///
/// Oh? You're approaching me?
///
#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;
const int N = 100010;
vector<int> A[N];
int st[N], ft[N], rt[N];
vector<pair<int,pii>> C[N];
int n, m;
namespace rmq
{
const int lg = 20;
vector<pii> vec;
pii a[lg][2*N];
int n;
void init(){
n = vec.size();
Loop(i,0,n) a[0][i] = vec[i];
Loop(k,0,lg-1) for(int i=0; i+(2<<k)<=n; ++i)
a[k+1][i] = min(a[k][i], a[k][i+(1<<k)]);
}
pii get(int l, int r){
int k = __lg(r-l);
return min(a[k][l], a[k][r-(1<<k)]);
}
}
void dfs1(int v, int p, int h, int& t){
st[v] = t++;
rt[v] = rmq::vec.size();
rmq::vec.emplace_back(h, v);
for(int u : A[v])
if(u != p)
dfs1(u, v, h+1, t),
rmq::vec.emplace_back(h, v);
ft[v] = t;
}
mt19937 rd(time(0));
struct node
{
node *l=0, *r=0;
int key, val, lzy=0;
int pri=rd();
node(int x, int y){key=x;val=y;}
};
void ppg(node* t){
if(t->lzy){
t->val += t->lzy;
if(t->l) t->l->lzy += t->lzy;
if(t->r) t->r->lzy += t->lzy;
t->lzy = 0;
}
}
int get(node* t, int k){
assert(t);
ppg(t);
if(k < t->key) return get(t->l, k);
if(k > t->key) return get(t->r, k);
return t->val;
}
node* merge(node* t, node* u){
if(!t) return u;
if(!u) return t;
if(t->pri > u->pri){
ppg(t);
t->r = merge(t->r, u);
return t;
} else {
ppg(u);
u->l = merge(t, u->l);
return u;
}
}
pair<int,node*> dfs2(int v, int p){
vector<int> st, cv;
vector<node*> ct;
int csum=0;
for(int u : A[v]){
if(u==p) continue;
st.push_back(::st[u]);
auto [x, y] = dfs2(u, v);
csum += x;
cv.push_back(x);
ct.push_back(y);
}
int ans = csum;
for(auto [w, pr] : C[v]){
auto [a, b] = pr;
int ca = upper_bound(st.begin(), st.end(), ::st[a])-st.begin()-1;
int cb = upper_bound(st.begin(), st.end(), ::st[b])-st.begin()-1;
int val = csum + w;
if(ca>=0) val += get(ct[ca], ::st[a])-cv[ca];
if(cb>=0) val += get(ct[cb], ::st[b])-cv[cb];
ans = max(ans, val);
}
node* t = new node(::st[v], csum);
Loop(i,0,ct.size()){
ct[i]->lzy += csum-cv[i];
t = merge(t, ct[i]);
}
return {ans, t};
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n;
Loop(i,1,n){
int v, u;
cin >> v >> u;
--v; --u;
A[v].push_back(u);
A[u].push_back(v);
}
dfs1(0, -1, 0, *new int(0));
rmq::init();
cin >> m;
Loop(i,0,m){
int a, b, x;
cin >> a >> b >> x;
--a; --b;
if(rt[a] > rt[b]) swap(a, b);
int lca = rmq::get(rt[a], rt[b]+1).second;
C[lca].push_back({x, {a, b}});
}
cout << dfs2(0, -1).first << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5032 KB |
Output is correct |
2 |
Correct |
3 ms |
5024 KB |
Output is correct |
3 |
Correct |
3 ms |
5068 KB |
Output is correct |
4 |
Correct |
3 ms |
5324 KB |
Output is correct |
5 |
Correct |
90 ms |
43060 KB |
Output is correct |
6 |
Correct |
98 ms |
63204 KB |
Output is correct |
7 |
Correct |
91 ms |
56292 KB |
Output is correct |
8 |
Correct |
67 ms |
43624 KB |
Output is correct |
9 |
Correct |
86 ms |
52412 KB |
Output is correct |
10 |
Correct |
76 ms |
43516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
5028 KB |
Output is correct |
3 |
Correct |
4 ms |
5580 KB |
Output is correct |
4 |
Correct |
129 ms |
66512 KB |
Output is correct |
5 |
Correct |
138 ms |
66444 KB |
Output is correct |
6 |
Correct |
117 ms |
66532 KB |
Output is correct |
7 |
Correct |
132 ms |
66448 KB |
Output is correct |
8 |
Correct |
121 ms |
66500 KB |
Output is correct |
9 |
Correct |
117 ms |
66464 KB |
Output is correct |
10 |
Correct |
153 ms |
66424 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
5028 KB |
Output is correct |
3 |
Correct |
4 ms |
5580 KB |
Output is correct |
4 |
Correct |
129 ms |
66512 KB |
Output is correct |
5 |
Correct |
138 ms |
66444 KB |
Output is correct |
6 |
Correct |
117 ms |
66532 KB |
Output is correct |
7 |
Correct |
132 ms |
66448 KB |
Output is correct |
8 |
Correct |
121 ms |
66500 KB |
Output is correct |
9 |
Correct |
117 ms |
66464 KB |
Output is correct |
10 |
Correct |
153 ms |
66424 KB |
Output is correct |
11 |
Correct |
11 ms |
6268 KB |
Output is correct |
12 |
Correct |
134 ms |
66752 KB |
Output is correct |
13 |
Correct |
147 ms |
66824 KB |
Output is correct |
14 |
Correct |
126 ms |
66800 KB |
Output is correct |
15 |
Correct |
124 ms |
66824 KB |
Output is correct |
16 |
Correct |
119 ms |
66792 KB |
Output is correct |
17 |
Correct |
127 ms |
66712 KB |
Output is correct |
18 |
Correct |
134 ms |
66728 KB |
Output is correct |
19 |
Correct |
130 ms |
66860 KB |
Output is correct |
20 |
Correct |
123 ms |
66740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
171 ms |
45800 KB |
Output is correct |
2 |
Correct |
119 ms |
66568 KB |
Output is correct |
3 |
Correct |
162 ms |
59088 KB |
Output is correct |
4 |
Correct |
149 ms |
46120 KB |
Output is correct |
5 |
Correct |
162 ms |
57876 KB |
Output is correct |
6 |
Correct |
134 ms |
46336 KB |
Output is correct |
7 |
Correct |
163 ms |
57180 KB |
Output is correct |
8 |
Correct |
163 ms |
46072 KB |
Output is correct |
9 |
Correct |
118 ms |
66564 KB |
Output is correct |
10 |
Correct |
198 ms |
54648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5032 KB |
Output is correct |
2 |
Correct |
3 ms |
5024 KB |
Output is correct |
3 |
Correct |
3 ms |
5068 KB |
Output is correct |
4 |
Correct |
3 ms |
5324 KB |
Output is correct |
5 |
Correct |
90 ms |
43060 KB |
Output is correct |
6 |
Correct |
98 ms |
63204 KB |
Output is correct |
7 |
Correct |
91 ms |
56292 KB |
Output is correct |
8 |
Correct |
67 ms |
43624 KB |
Output is correct |
9 |
Correct |
86 ms |
52412 KB |
Output is correct |
10 |
Correct |
76 ms |
43516 KB |
Output is correct |
11 |
Correct |
5 ms |
5296 KB |
Output is correct |
12 |
Correct |
4 ms |
5552 KB |
Output is correct |
13 |
Correct |
3 ms |
5556 KB |
Output is correct |
14 |
Correct |
3 ms |
5424 KB |
Output is correct |
15 |
Correct |
3 ms |
5428 KB |
Output is correct |
16 |
Correct |
4 ms |
5452 KB |
Output is correct |
17 |
Correct |
4 ms |
5428 KB |
Output is correct |
18 |
Correct |
4 ms |
5536 KB |
Output is correct |
19 |
Correct |
3 ms |
5324 KB |
Output is correct |
20 |
Correct |
4 ms |
5580 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5032 KB |
Output is correct |
2 |
Correct |
3 ms |
5024 KB |
Output is correct |
3 |
Correct |
3 ms |
5068 KB |
Output is correct |
4 |
Correct |
3 ms |
5324 KB |
Output is correct |
5 |
Correct |
90 ms |
43060 KB |
Output is correct |
6 |
Correct |
98 ms |
63204 KB |
Output is correct |
7 |
Correct |
91 ms |
56292 KB |
Output is correct |
8 |
Correct |
67 ms |
43624 KB |
Output is correct |
9 |
Correct |
86 ms |
52412 KB |
Output is correct |
10 |
Correct |
76 ms |
43516 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
5028 KB |
Output is correct |
13 |
Correct |
4 ms |
5580 KB |
Output is correct |
14 |
Correct |
129 ms |
66512 KB |
Output is correct |
15 |
Correct |
138 ms |
66444 KB |
Output is correct |
16 |
Correct |
117 ms |
66532 KB |
Output is correct |
17 |
Correct |
132 ms |
66448 KB |
Output is correct |
18 |
Correct |
121 ms |
66500 KB |
Output is correct |
19 |
Correct |
117 ms |
66464 KB |
Output is correct |
20 |
Correct |
153 ms |
66424 KB |
Output is correct |
21 |
Correct |
11 ms |
6268 KB |
Output is correct |
22 |
Correct |
134 ms |
66752 KB |
Output is correct |
23 |
Correct |
147 ms |
66824 KB |
Output is correct |
24 |
Correct |
126 ms |
66800 KB |
Output is correct |
25 |
Correct |
124 ms |
66824 KB |
Output is correct |
26 |
Correct |
119 ms |
66792 KB |
Output is correct |
27 |
Correct |
127 ms |
66712 KB |
Output is correct |
28 |
Correct |
134 ms |
66728 KB |
Output is correct |
29 |
Correct |
130 ms |
66860 KB |
Output is correct |
30 |
Correct |
123 ms |
66740 KB |
Output is correct |
31 |
Correct |
171 ms |
45800 KB |
Output is correct |
32 |
Correct |
119 ms |
66568 KB |
Output is correct |
33 |
Correct |
162 ms |
59088 KB |
Output is correct |
34 |
Correct |
149 ms |
46120 KB |
Output is correct |
35 |
Correct |
162 ms |
57876 KB |
Output is correct |
36 |
Correct |
134 ms |
46336 KB |
Output is correct |
37 |
Correct |
163 ms |
57180 KB |
Output is correct |
38 |
Correct |
163 ms |
46072 KB |
Output is correct |
39 |
Correct |
118 ms |
66564 KB |
Output is correct |
40 |
Correct |
198 ms |
54648 KB |
Output is correct |
41 |
Correct |
5 ms |
5296 KB |
Output is correct |
42 |
Correct |
4 ms |
5552 KB |
Output is correct |
43 |
Correct |
3 ms |
5556 KB |
Output is correct |
44 |
Correct |
3 ms |
5424 KB |
Output is correct |
45 |
Correct |
3 ms |
5428 KB |
Output is correct |
46 |
Correct |
4 ms |
5452 KB |
Output is correct |
47 |
Correct |
4 ms |
5428 KB |
Output is correct |
48 |
Correct |
4 ms |
5536 KB |
Output is correct |
49 |
Correct |
3 ms |
5324 KB |
Output is correct |
50 |
Correct |
4 ms |
5580 KB |
Output is correct |
51 |
Correct |
175 ms |
46388 KB |
Output is correct |
52 |
Correct |
129 ms |
66756 KB |
Output is correct |
53 |
Correct |
172 ms |
55452 KB |
Output is correct |
54 |
Correct |
120 ms |
46484 KB |
Output is correct |
55 |
Correct |
178 ms |
45980 KB |
Output is correct |
56 |
Correct |
144 ms |
66828 KB |
Output is correct |
57 |
Correct |
183 ms |
56592 KB |
Output is correct |
58 |
Correct |
158 ms |
46528 KB |
Output is correct |
59 |
Correct |
173 ms |
46404 KB |
Output is correct |
60 |
Correct |
130 ms |
66768 KB |
Output is correct |
61 |
Correct |
153 ms |
56752 KB |
Output is correct |
62 |
Correct |
153 ms |
46472 KB |
Output is correct |
63 |
Correct |
192 ms |
45952 KB |
Output is correct |
64 |
Correct |
135 ms |
66704 KB |
Output is correct |
65 |
Correct |
188 ms |
56688 KB |
Output is correct |
66 |
Correct |
116 ms |
46456 KB |
Output is correct |
67 |
Correct |
163 ms |
46008 KB |
Output is correct |
68 |
Correct |
132 ms |
66792 KB |
Output is correct |
69 |
Correct |
148 ms |
53640 KB |
Output is correct |
70 |
Correct |
139 ms |
46620 KB |
Output is correct |