#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
#define int ll
const int N=4e5+99,lg=20;
int n,m,cnt=1,st[N],ft[N],h[N],a[N],dp[N],pd[N],par[lg][N],fenwik[N];
vector<int> emp,g[N];
vector<pair<int,int>> solo[N];
vector<vector<int>> duo[N];
void add(int x,int val){
for(x++;x<N;x+=x&-x) fenwik[x]+=val;
}
void add(int l,int r,int val){
//cout<<l<<" "<<r<<" : "<<val<<endl;
add(l,val);
add(r,-val);
}
int get(int x){
int res=0;
for(x++;x>0;x-=x&-x) res+=fenwik[x];
return res;
}
int LCA(int u,int v,int &x,int &y){
f_(l,lg-1,0){
if(h[u]<=h[par[l][v]]){
v=par[l][v];
}
}
if(u==v) return u;
f_(l,lg-1,0){
if(par[l][u]!=par[l][v]){
u=par[l][u],v=par[l][v];
}
}
x=u,y=v;
return par[0][u];
}
void dfs1(int u,int p){
par[0][u]=p; f(l,1,lg) par[l][u]=par[l-1][par[l-1][u]];
st[u]=cnt++;
for(auto v : g[u]){
if(v==p) continue ;
h[v]=h[u]+1;
dfs1(v,u);
}
ft[u]=cnt;
}
void dfs2(int u,int p){
for(auto v : g[u]){
if(v==p) continue ;
dfs2(v,u);
dp[u]+=dp[v];
pd[u]+=dp[v];
add(st[u]+1,ft[u],dp[v]);
add(st[v],ft[v],-dp[v]);
}
for(auto v : solo[u]){
maxm(dp[u],get(st[v.F])+pd[v.F]+v.S-get(st[u]));
}
for(auto vec : duo[u]){
int sum=pd[vec[0]]+pd[vec[1]];
maxm(dp[u],get(st[vec[0]])+get(st[vec[1]])-pd[u]+vec[4]+sum-2*get(st[u]));
/*if(dp[u]==29){
dbgv(vec);
eror(get(st[vec[0]])-get(st[u]));
eror(get(st[vec[1]])-get(st[u]));
exit(0);
}*/
}
//cout<<u<<" -> "<<dp[u]<<endl;
}
main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n;
f(i,1,n){
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
dfs1(1,1);
cin>>m;
f(i,0,m){
int u,v,x=0,y=0,cost;
cin>>u>>v>>cost;
if(h[u]>h[v]) swap(u,v);
int lca=LCA(u,v,x,y);
//cout<<u<<" "<<v<<" -> "<<lca<<" "<<x<<" "<<y<<endl;
if(lca==u){
solo[u].pb({v,cost});
continue ;
}
duo[lca].pb(emp);
duo[lca].back().pb(u);
duo[lca].back().pb(v);
duo[lca].back().pb(x);
duo[lca].back().pb(y);
duo[lca].back().pb(cost);
}
dfs2(1,1);
cout<<dp[1];
}
Compilation message
election_campaign.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
93 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28748 KB |
Output is correct |
2 |
Correct |
15 ms |
28748 KB |
Output is correct |
3 |
Correct |
16 ms |
28748 KB |
Output is correct |
4 |
Correct |
15 ms |
28960 KB |
Output is correct |
5 |
Correct |
113 ms |
53828 KB |
Output is correct |
6 |
Correct |
64 ms |
62368 KB |
Output is correct |
7 |
Correct |
119 ms |
59588 KB |
Output is correct |
8 |
Correct |
105 ms |
52528 KB |
Output is correct |
9 |
Correct |
135 ms |
57684 KB |
Output is correct |
10 |
Correct |
96 ms |
52484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28692 KB |
Output is correct |
2 |
Correct |
15 ms |
28636 KB |
Output is correct |
3 |
Correct |
16 ms |
29020 KB |
Output is correct |
4 |
Correct |
167 ms |
65056 KB |
Output is correct |
5 |
Correct |
198 ms |
65104 KB |
Output is correct |
6 |
Correct |
234 ms |
65084 KB |
Output is correct |
7 |
Correct |
178 ms |
65020 KB |
Output is correct |
8 |
Correct |
218 ms |
65076 KB |
Output is correct |
9 |
Correct |
206 ms |
65028 KB |
Output is correct |
10 |
Correct |
216 ms |
65084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28692 KB |
Output is correct |
2 |
Correct |
15 ms |
28636 KB |
Output is correct |
3 |
Correct |
16 ms |
29020 KB |
Output is correct |
4 |
Correct |
167 ms |
65056 KB |
Output is correct |
5 |
Correct |
198 ms |
65104 KB |
Output is correct |
6 |
Correct |
234 ms |
65084 KB |
Output is correct |
7 |
Correct |
178 ms |
65020 KB |
Output is correct |
8 |
Correct |
218 ms |
65076 KB |
Output is correct |
9 |
Correct |
206 ms |
65028 KB |
Output is correct |
10 |
Correct |
216 ms |
65084 KB |
Output is correct |
11 |
Correct |
33 ms |
29904 KB |
Output is correct |
12 |
Correct |
180 ms |
64960 KB |
Output is correct |
13 |
Correct |
183 ms |
65100 KB |
Output is correct |
14 |
Correct |
182 ms |
65048 KB |
Output is correct |
15 |
Correct |
176 ms |
65028 KB |
Output is correct |
16 |
Correct |
185 ms |
65084 KB |
Output is correct |
17 |
Correct |
174 ms |
64924 KB |
Output is correct |
18 |
Correct |
179 ms |
65016 KB |
Output is correct |
19 |
Correct |
229 ms |
65060 KB |
Output is correct |
20 |
Correct |
194 ms |
64956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
395 ms |
64116 KB |
Output is correct |
2 |
Correct |
226 ms |
65080 KB |
Output is correct |
3 |
Correct |
438 ms |
65664 KB |
Output is correct |
4 |
Correct |
262 ms |
62712 KB |
Output is correct |
5 |
Correct |
386 ms |
62708 KB |
Output is correct |
6 |
Correct |
264 ms |
62780 KB |
Output is correct |
7 |
Correct |
452 ms |
65440 KB |
Output is correct |
8 |
Correct |
412 ms |
58872 KB |
Output is correct |
9 |
Correct |
218 ms |
65088 KB |
Output is correct |
10 |
Correct |
416 ms |
65084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28748 KB |
Output is correct |
2 |
Correct |
15 ms |
28748 KB |
Output is correct |
3 |
Correct |
16 ms |
28748 KB |
Output is correct |
4 |
Correct |
15 ms |
28960 KB |
Output is correct |
5 |
Correct |
113 ms |
53828 KB |
Output is correct |
6 |
Correct |
64 ms |
62368 KB |
Output is correct |
7 |
Correct |
119 ms |
59588 KB |
Output is correct |
8 |
Correct |
105 ms |
52528 KB |
Output is correct |
9 |
Correct |
135 ms |
57684 KB |
Output is correct |
10 |
Correct |
96 ms |
52484 KB |
Output is correct |
11 |
Correct |
16 ms |
29028 KB |
Output is correct |
12 |
Correct |
20 ms |
29068 KB |
Output is correct |
13 |
Correct |
18 ms |
29048 KB |
Output is correct |
14 |
Correct |
17 ms |
29004 KB |
Output is correct |
15 |
Correct |
16 ms |
29032 KB |
Output is correct |
16 |
Correct |
17 ms |
29060 KB |
Output is correct |
17 |
Correct |
17 ms |
29004 KB |
Output is correct |
18 |
Correct |
16 ms |
29004 KB |
Output is correct |
19 |
Correct |
16 ms |
29004 KB |
Output is correct |
20 |
Correct |
15 ms |
29032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28748 KB |
Output is correct |
2 |
Correct |
15 ms |
28748 KB |
Output is correct |
3 |
Correct |
16 ms |
28748 KB |
Output is correct |
4 |
Correct |
15 ms |
28960 KB |
Output is correct |
5 |
Correct |
113 ms |
53828 KB |
Output is correct |
6 |
Correct |
64 ms |
62368 KB |
Output is correct |
7 |
Correct |
119 ms |
59588 KB |
Output is correct |
8 |
Correct |
105 ms |
52528 KB |
Output is correct |
9 |
Correct |
135 ms |
57684 KB |
Output is correct |
10 |
Correct |
96 ms |
52484 KB |
Output is correct |
11 |
Correct |
15 ms |
28692 KB |
Output is correct |
12 |
Correct |
15 ms |
28636 KB |
Output is correct |
13 |
Correct |
16 ms |
29020 KB |
Output is correct |
14 |
Correct |
167 ms |
65056 KB |
Output is correct |
15 |
Correct |
198 ms |
65104 KB |
Output is correct |
16 |
Correct |
234 ms |
65084 KB |
Output is correct |
17 |
Correct |
178 ms |
65020 KB |
Output is correct |
18 |
Correct |
218 ms |
65076 KB |
Output is correct |
19 |
Correct |
206 ms |
65028 KB |
Output is correct |
20 |
Correct |
216 ms |
65084 KB |
Output is correct |
21 |
Correct |
33 ms |
29904 KB |
Output is correct |
22 |
Correct |
180 ms |
64960 KB |
Output is correct |
23 |
Correct |
183 ms |
65100 KB |
Output is correct |
24 |
Correct |
182 ms |
65048 KB |
Output is correct |
25 |
Correct |
176 ms |
65028 KB |
Output is correct |
26 |
Correct |
185 ms |
65084 KB |
Output is correct |
27 |
Correct |
174 ms |
64924 KB |
Output is correct |
28 |
Correct |
179 ms |
65016 KB |
Output is correct |
29 |
Correct |
229 ms |
65060 KB |
Output is correct |
30 |
Correct |
194 ms |
64956 KB |
Output is correct |
31 |
Correct |
395 ms |
64116 KB |
Output is correct |
32 |
Correct |
226 ms |
65080 KB |
Output is correct |
33 |
Correct |
438 ms |
65664 KB |
Output is correct |
34 |
Correct |
262 ms |
62712 KB |
Output is correct |
35 |
Correct |
386 ms |
62708 KB |
Output is correct |
36 |
Correct |
264 ms |
62780 KB |
Output is correct |
37 |
Correct |
452 ms |
65440 KB |
Output is correct |
38 |
Correct |
412 ms |
58872 KB |
Output is correct |
39 |
Correct |
218 ms |
65088 KB |
Output is correct |
40 |
Correct |
416 ms |
65084 KB |
Output is correct |
41 |
Correct |
16 ms |
29028 KB |
Output is correct |
42 |
Correct |
20 ms |
29068 KB |
Output is correct |
43 |
Correct |
18 ms |
29048 KB |
Output is correct |
44 |
Correct |
17 ms |
29004 KB |
Output is correct |
45 |
Correct |
16 ms |
29032 KB |
Output is correct |
46 |
Correct |
17 ms |
29060 KB |
Output is correct |
47 |
Correct |
17 ms |
29004 KB |
Output is correct |
48 |
Correct |
16 ms |
29004 KB |
Output is correct |
49 |
Correct |
16 ms |
29004 KB |
Output is correct |
50 |
Correct |
15 ms |
29032 KB |
Output is correct |
51 |
Correct |
400 ms |
58836 KB |
Output is correct |
52 |
Correct |
224 ms |
65012 KB |
Output is correct |
53 |
Correct |
431 ms |
65192 KB |
Output is correct |
54 |
Correct |
298 ms |
57128 KB |
Output is correct |
55 |
Correct |
415 ms |
64328 KB |
Output is correct |
56 |
Correct |
183 ms |
65052 KB |
Output is correct |
57 |
Correct |
472 ms |
62272 KB |
Output is correct |
58 |
Correct |
274 ms |
62708 KB |
Output is correct |
59 |
Correct |
409 ms |
58800 KB |
Output is correct |
60 |
Correct |
168 ms |
65028 KB |
Output is correct |
61 |
Correct |
435 ms |
62256 KB |
Output is correct |
62 |
Correct |
253 ms |
62712 KB |
Output is correct |
63 |
Correct |
419 ms |
64388 KB |
Output is correct |
64 |
Correct |
165 ms |
64932 KB |
Output is correct |
65 |
Correct |
456 ms |
65360 KB |
Output is correct |
66 |
Correct |
331 ms |
57024 KB |
Output is correct |
67 |
Correct |
398 ms |
64044 KB |
Output is correct |
68 |
Correct |
204 ms |
65060 KB |
Output is correct |
69 |
Correct |
410 ms |
60968 KB |
Output is correct |
70 |
Correct |
301 ms |
62796 KB |
Output is correct |