#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n,m;
llo ac,bc,dd;
llo par[100001][20];
llo lev[100001];
vector<llo> adj[100001];
llo co=0;
llo st[100001];
llo en[100001];
llo dp[100001];
llo tree[400001];
llo lazy[400001];
vector<pair<pair<llo,llo>,pair<llo,llo>>> pre[100001];
vector<llo> pre2[100001];
void update(llo no,llo l,llo r,llo aa,llo bb,llo val){
if(lazy[no]!=0){
tree[no]+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
}
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
tree[no]+=val;
if(l<r){
tree[no*2+1]+=val;
tree[no*2+2]+=val;
}
}
else{
llo mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,val);
update(no*2+2,mid+1,r,aa,bb,val);
tree[no]=tree[no*2+1]+tree[no*2+2];
}
}
llo query(llo no,llo l,llo r,llo i){
if(lazy[no]!=0){
tree[no]+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
}
if(l==r){
return tree[no];
}
llo mid=(l+r)/2;
if(i<=mid){
return query(no*2+1,l,mid,i);
}
else{
return query(no*2+2,mid+1,r,i);
}
}
llo dfs(llo no,llo par2=-1,llo levv=0){
st[no]=co;
co+=1;
par[no][0]=par2;
lev[no]=levv;
for(auto j:adj[no]){
if(j==par2){
continue;
}
dfs(j,no,levv+1);
}
en[no]=co-1;
}
llo kk(llo aa,llo k){
for(llo j=19;j>=0;j--){
if((1<<j)&k){
aa=par[aa][j];
}
}
return aa;
}
pair<llo,pair<llo,llo>> lca(llo aa,llo bb){
llo cc,dd;
cc=aa;
dd=bb;
if(lev[aa]>lev[bb]){
aa=kk(aa,abs(lev[bb]-lev[aa]));
if(aa==bb){
return {aa,{kk(cc,abs(lev[bb]-lev[cc])-1),-1}};
}
}
else{
bb=kk(bb,abs(lev[bb]-lev[aa]));
if(aa==bb){
return {aa,{-1,kk(dd,abs(lev[bb]-lev[dd])-1)}};
}
}
for(llo j=19;j>=0;j--){
if(par[aa][j]!=par[bb][j]){
aa=par[aa][j];
bb=par[bb][j];
}
}
return {par[aa][0],{kk(cc,abs(lev[cc]-lev[par[aa][0]])-1),kk(dd,abs(lev[dd]-lev[par[aa][0]])-1)}};
}
llo dfs2(llo no,llo par2=-1){
llo su=0;
for(auto j:adj[no]){
if(j!=par2){
dfs2(j,no);
su+=dp[j];
}
}
dp[no]=su;
for(llo j=0;j<pre[no].size();j++){
pair<pair<llo,llo>,pair<llo,llo>> kk=pre[no][j];
llo cost=pre2[no][j];
if(kk.b.a==-1){
cost+=su;
cost-=dp[kk.b.b];
cost+=query(0,0,n-1,st[kk.a.b]);
}
else if(kk.b.b==-1){
cost+=su;
cost-=dp[kk.b.a];
cost+=query(0,0,n-1,st[kk.a.a]);
}
else{
cost+=su;
cost-=dp[kk.b.b];
cost-=dp[kk.b.a];
cost+=query(0,0,n-1,st[kk.a.b]);
cost+=query(0,0,n-1,st[kk.a.a]);
}
dp[no]=max(dp[no],cost);
}
update(0,0,n-1,st[no],st[no],su);
for(auto j:adj[no]){
if(j==par2){
continue;
}
update(0,0,n-1,st[j],en[j],su-dp[j]);
}
}
int main(){
memset(tree,0,sizeof(tree));
memset(lazy,0,sizeof(lazy));
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(llo i=0;i<n-1;i++){
cin>>ac>>bc;
adj[ac-1].pb(bc-1);
adj[bc-1].pb(ac-1);
}
dfs(0);
cin>>m;
for(llo j=1;j<20;j++){
for(llo i=0;i<n;i++){
if(par[i][j-1]==-1){
par[i][j]=-1;
}
else{
par[i][j]=par[par[i][j-1]][j-1];
}
}
}
for(llo i=0;i<m;i++){
cin>>ac>>bc>>dd;
pair<llo,pair<llo,llo>> cc=lca(ac-1,bc-1);
pre[cc.a].pb({{ac-1,bc-1},cc.b});
pre2[cc.a].pb(dd);
// cout<<cc.a<<","<<cc.b.a<<","<<cc.b.b<<endl;
}
dfs2(0);
cout<<dp[0]<<endl;
return 0;
}
Compilation message
election_campaign.cpp: In function 'llo dfs(llo, llo, llo)':
election_campaign.cpp:79:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
election_campaign.cpp: In function 'llo dfs2(llo, llo)':
election_campaign.cpp:121:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(llo j=0;j<pre[no].size();j++){
~^~~~~~~~~~~~~~~
election_campaign.cpp:151:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
13696 KB |
Output is correct |
2 |
Correct |
12 ms |
13696 KB |
Output is correct |
3 |
Correct |
12 ms |
13696 KB |
Output is correct |
4 |
Correct |
16 ms |
13952 KB |
Output is correct |
5 |
Incorrect |
185 ms |
36984 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
13696 KB |
Output is correct |
2 |
Correct |
13 ms |
13696 KB |
Output is correct |
3 |
Correct |
13 ms |
13952 KB |
Output is correct |
4 |
Correct |
269 ms |
50040 KB |
Output is correct |
5 |
Correct |
279 ms |
50168 KB |
Output is correct |
6 |
Correct |
239 ms |
50056 KB |
Output is correct |
7 |
Correct |
258 ms |
50296 KB |
Output is correct |
8 |
Correct |
261 ms |
50040 KB |
Output is correct |
9 |
Correct |
245 ms |
50100 KB |
Output is correct |
10 |
Correct |
266 ms |
50080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
13696 KB |
Output is correct |
2 |
Correct |
13 ms |
13696 KB |
Output is correct |
3 |
Correct |
13 ms |
13952 KB |
Output is correct |
4 |
Correct |
269 ms |
50040 KB |
Output is correct |
5 |
Correct |
279 ms |
50168 KB |
Output is correct |
6 |
Correct |
239 ms |
50056 KB |
Output is correct |
7 |
Correct |
258 ms |
50296 KB |
Output is correct |
8 |
Correct |
261 ms |
50040 KB |
Output is correct |
9 |
Correct |
245 ms |
50100 KB |
Output is correct |
10 |
Correct |
266 ms |
50080 KB |
Output is correct |
11 |
Correct |
26 ms |
15744 KB |
Output is correct |
12 |
Correct |
276 ms |
50040 KB |
Output is correct |
13 |
Correct |
262 ms |
50172 KB |
Output is correct |
14 |
Correct |
232 ms |
50040 KB |
Output is correct |
15 |
Correct |
262 ms |
50144 KB |
Output is correct |
16 |
Correct |
214 ms |
50036 KB |
Output is correct |
17 |
Correct |
288 ms |
50196 KB |
Output is correct |
18 |
Correct |
273 ms |
50044 KB |
Output is correct |
19 |
Correct |
229 ms |
50040 KB |
Output is correct |
20 |
Correct |
290 ms |
50264 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
295 ms |
41560 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
13696 KB |
Output is correct |
2 |
Correct |
12 ms |
13696 KB |
Output is correct |
3 |
Correct |
12 ms |
13696 KB |
Output is correct |
4 |
Correct |
16 ms |
13952 KB |
Output is correct |
5 |
Incorrect |
185 ms |
36984 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
13696 KB |
Output is correct |
2 |
Correct |
12 ms |
13696 KB |
Output is correct |
3 |
Correct |
12 ms |
13696 KB |
Output is correct |
4 |
Correct |
16 ms |
13952 KB |
Output is correct |
5 |
Incorrect |
185 ms |
36984 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |