#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=1e5+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()
//input
ll n,m,x,y,c;
vector<ll> v[N],lis;
//tree
ll height[N],depth[N],sz[N],top[N],to[N],ti,fa[N],dg[N];
vector<pair<ll,pll> > q[N];
//segment tree
ll seg[4*N];
//dp
ll dp[N];
queue<ll> que;
void PDFS(ll nd,ll pa){
sz[nd]=1;
depth[nd]=depth[fa[nd]=pa]+1;
for(ll i:v[nd]){
if(i==pa)continue;
PDFS(i,nd);
height[nd]=max(height[nd],height[i]+1);
sz[nd]+=sz[i];
}
}
void DFS(ll nd,ll pa){
ll id=-1;
to[nd]=ti++;
for(ll i:v[nd]){
if(i==pa)continue;
id=(id==-1?i:(sz[id]<sz[i]?i:id));
}
if(id==-1)return ;
top[id]=top[nd];
DFS(id,nd);
for(ll i:v[nd]){
if(i==pa||i==id)continue;
top[i]=i;
DFS(i,nd);
}
}
ll lca(ll nda,ll ndb){
while(top[nda]!=top[ndb]){
if(depth[top[nda]]<depth[top[ndb]])swap(nda,ndb);
nda=fa[top[nda]];
}
return (depth[nda]<depth[ndb]?nda:ndb);
}
ll sum(ll id,ll l,ll r,ll ql,ll qr){
if(l>=ql&&r<=qr)return seg[id];
if(l>=qr||r<=ql)return 0;
ll mid=(l+r)/2;
return sum(id*2,l,mid,ql,qr)+sum(id*2+1,mid,r,ql,qr);
}
void ins(ll id,ll l,ll r,ll t,ll d){
if(l==r-1){seg[id]+=d;return;}
ll mid=(l+r)/2;
if(t<mid){ins(id*2,l,mid,t,d);}else{ins(id*2+1,mid,r,t,d);}
seg[id]=seg[id*2]+seg[id*2+1];
}
ll Q(ll nda,ll ndb){
ll res=0;
while(top[ndb]!=top[nda]){
res+=sum(1,0,n,to[top[ndb]],to[ndb]+1);
ndb=fa[top[ndb]];
}
return res+sum(1,0,n,to[nda],to[ndb]+1);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
depth[0]=-1;top[1]=1;
cin>>n;
REP(i,n-1)cin>>x>>y,v[x].pb(y),v[y].pb(x);
PDFS(1,0);
DFS(1,0);
cin>>m;
REP(i,m){
cin>>x>>y>>c;
q[lca(x,y)].pb(mp(c,mp(x,y)));
}
REP1(i,n){
dg[i]=SZ(v[i]);
if(dg[i]==1&&i!=1)que.push(i);
}
dg[1]=SZ(v[1])+1;
while(SZ(que)){
ll i=que.front();que.pop();
dp[i]=Q(i,i);
for(auto j:q[i]){
dp[i]=max(dp[i],j.X+Q(i,j.Y.X)+Q(i,j.Y.Y)-Q(i,i));
}
ins(1,0,n,to[i],-dp[i]);
ins(1,0,n,to[fa[i]],dp[i]);
for(auto j:v[i]){
--dg[j];
if(dg[j]==1)que.push(j);
}
}
cout<<dp[1]<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
5 ms |
5248 KB |
Output is correct |
5 |
Correct |
205 ms |
18904 KB |
Output is correct |
6 |
Correct |
87 ms |
22264 KB |
Output is correct |
7 |
Correct |
173 ms |
21240 KB |
Output is correct |
8 |
Correct |
143 ms |
18808 KB |
Output is correct |
9 |
Correct |
183 ms |
20344 KB |
Output is correct |
10 |
Correct |
128 ms |
18680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
3 ms |
5120 KB |
Output is correct |
3 |
Correct |
5 ms |
5248 KB |
Output is correct |
4 |
Correct |
213 ms |
27128 KB |
Output is correct |
5 |
Correct |
219 ms |
27236 KB |
Output is correct |
6 |
Correct |
225 ms |
27296 KB |
Output is correct |
7 |
Correct |
195 ms |
27128 KB |
Output is correct |
8 |
Correct |
240 ms |
27128 KB |
Output is correct |
9 |
Correct |
199 ms |
27212 KB |
Output is correct |
10 |
Correct |
209 ms |
27128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
3 ms |
5120 KB |
Output is correct |
3 |
Correct |
5 ms |
5248 KB |
Output is correct |
4 |
Correct |
213 ms |
27128 KB |
Output is correct |
5 |
Correct |
219 ms |
27236 KB |
Output is correct |
6 |
Correct |
225 ms |
27296 KB |
Output is correct |
7 |
Correct |
195 ms |
27128 KB |
Output is correct |
8 |
Correct |
240 ms |
27128 KB |
Output is correct |
9 |
Correct |
199 ms |
27212 KB |
Output is correct |
10 |
Correct |
209 ms |
27128 KB |
Output is correct |
11 |
Correct |
19 ms |
6400 KB |
Output is correct |
12 |
Correct |
202 ms |
27540 KB |
Output is correct |
13 |
Correct |
201 ms |
27392 KB |
Output is correct |
14 |
Correct |
192 ms |
27428 KB |
Output is correct |
15 |
Correct |
193 ms |
27416 KB |
Output is correct |
16 |
Correct |
185 ms |
27512 KB |
Output is correct |
17 |
Correct |
196 ms |
27384 KB |
Output is correct |
18 |
Correct |
202 ms |
27512 KB |
Output is correct |
19 |
Correct |
192 ms |
27512 KB |
Output is correct |
20 |
Correct |
208 ms |
27512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
537 ms |
22736 KB |
Output is correct |
2 |
Correct |
205 ms |
27256 KB |
Output is correct |
3 |
Correct |
345 ms |
25932 KB |
Output is correct |
4 |
Correct |
265 ms |
22472 KB |
Output is correct |
5 |
Correct |
337 ms |
25396 KB |
Output is correct |
6 |
Correct |
290 ms |
22372 KB |
Output is correct |
7 |
Correct |
368 ms |
25264 KB |
Output is correct |
8 |
Correct |
402 ms |
23136 KB |
Output is correct |
9 |
Correct |
181 ms |
27164 KB |
Output is correct |
10 |
Correct |
311 ms |
24488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
5 ms |
5248 KB |
Output is correct |
5 |
Correct |
205 ms |
18904 KB |
Output is correct |
6 |
Correct |
87 ms |
22264 KB |
Output is correct |
7 |
Correct |
173 ms |
21240 KB |
Output is correct |
8 |
Correct |
143 ms |
18808 KB |
Output is correct |
9 |
Correct |
183 ms |
20344 KB |
Output is correct |
10 |
Correct |
128 ms |
18680 KB |
Output is correct |
11 |
Correct |
6 ms |
5280 KB |
Output is correct |
12 |
Correct |
9 ms |
5248 KB |
Output is correct |
13 |
Correct |
6 ms |
5248 KB |
Output is correct |
14 |
Correct |
5 ms |
5248 KB |
Output is correct |
15 |
Correct |
6 ms |
5248 KB |
Output is correct |
16 |
Correct |
5 ms |
5248 KB |
Output is correct |
17 |
Correct |
6 ms |
5248 KB |
Output is correct |
18 |
Correct |
6 ms |
5248 KB |
Output is correct |
19 |
Correct |
5 ms |
5280 KB |
Output is correct |
20 |
Correct |
6 ms |
5256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
5 ms |
5248 KB |
Output is correct |
5 |
Correct |
205 ms |
18904 KB |
Output is correct |
6 |
Correct |
87 ms |
22264 KB |
Output is correct |
7 |
Correct |
173 ms |
21240 KB |
Output is correct |
8 |
Correct |
143 ms |
18808 KB |
Output is correct |
9 |
Correct |
183 ms |
20344 KB |
Output is correct |
10 |
Correct |
128 ms |
18680 KB |
Output is correct |
11 |
Correct |
4 ms |
5120 KB |
Output is correct |
12 |
Correct |
3 ms |
5120 KB |
Output is correct |
13 |
Correct |
5 ms |
5248 KB |
Output is correct |
14 |
Correct |
213 ms |
27128 KB |
Output is correct |
15 |
Correct |
219 ms |
27236 KB |
Output is correct |
16 |
Correct |
225 ms |
27296 KB |
Output is correct |
17 |
Correct |
195 ms |
27128 KB |
Output is correct |
18 |
Correct |
240 ms |
27128 KB |
Output is correct |
19 |
Correct |
199 ms |
27212 KB |
Output is correct |
20 |
Correct |
209 ms |
27128 KB |
Output is correct |
21 |
Correct |
19 ms |
6400 KB |
Output is correct |
22 |
Correct |
202 ms |
27540 KB |
Output is correct |
23 |
Correct |
201 ms |
27392 KB |
Output is correct |
24 |
Correct |
192 ms |
27428 KB |
Output is correct |
25 |
Correct |
193 ms |
27416 KB |
Output is correct |
26 |
Correct |
185 ms |
27512 KB |
Output is correct |
27 |
Correct |
196 ms |
27384 KB |
Output is correct |
28 |
Correct |
202 ms |
27512 KB |
Output is correct |
29 |
Correct |
192 ms |
27512 KB |
Output is correct |
30 |
Correct |
208 ms |
27512 KB |
Output is correct |
31 |
Correct |
537 ms |
22736 KB |
Output is correct |
32 |
Correct |
205 ms |
27256 KB |
Output is correct |
33 |
Correct |
345 ms |
25932 KB |
Output is correct |
34 |
Correct |
265 ms |
22472 KB |
Output is correct |
35 |
Correct |
337 ms |
25396 KB |
Output is correct |
36 |
Correct |
290 ms |
22372 KB |
Output is correct |
37 |
Correct |
368 ms |
25264 KB |
Output is correct |
38 |
Correct |
402 ms |
23136 KB |
Output is correct |
39 |
Correct |
181 ms |
27164 KB |
Output is correct |
40 |
Correct |
311 ms |
24488 KB |
Output is correct |
41 |
Correct |
6 ms |
5280 KB |
Output is correct |
42 |
Correct |
9 ms |
5248 KB |
Output is correct |
43 |
Correct |
6 ms |
5248 KB |
Output is correct |
44 |
Correct |
5 ms |
5248 KB |
Output is correct |
45 |
Correct |
6 ms |
5248 KB |
Output is correct |
46 |
Correct |
5 ms |
5248 KB |
Output is correct |
47 |
Correct |
6 ms |
5248 KB |
Output is correct |
48 |
Correct |
6 ms |
5248 KB |
Output is correct |
49 |
Correct |
5 ms |
5280 KB |
Output is correct |
50 |
Correct |
6 ms |
5256 KB |
Output is correct |
51 |
Correct |
437 ms |
23472 KB |
Output is correct |
52 |
Correct |
216 ms |
27484 KB |
Output is correct |
53 |
Correct |
381 ms |
24904 KB |
Output is correct |
54 |
Correct |
281 ms |
22728 KB |
Output is correct |
55 |
Correct |
607 ms |
22956 KB |
Output is correct |
56 |
Correct |
210 ms |
27512 KB |
Output is correct |
57 |
Correct |
325 ms |
25592 KB |
Output is correct |
58 |
Correct |
275 ms |
22752 KB |
Output is correct |
59 |
Correct |
434 ms |
23408 KB |
Output is correct |
60 |
Correct |
207 ms |
27384 KB |
Output is correct |
61 |
Correct |
327 ms |
25500 KB |
Output is correct |
62 |
Correct |
287 ms |
22600 KB |
Output is correct |
63 |
Correct |
561 ms |
23044 KB |
Output is correct |
64 |
Correct |
256 ms |
27408 KB |
Output is correct |
65 |
Correct |
365 ms |
25356 KB |
Output is correct |
66 |
Correct |
248 ms |
22568 KB |
Output is correct |
67 |
Correct |
505 ms |
23056 KB |
Output is correct |
68 |
Correct |
214 ms |
27384 KB |
Output is correct |
69 |
Correct |
293 ms |
24756 KB |
Output is correct |
70 |
Correct |
269 ms |
22676 KB |
Output is correct |