#include <bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int n,q,sprs[N][20],lvl[N],dpsons[N],dp[N],par[N],sz[N],l,r;
vector <long long> v[N],pfx[N][2];
vector <pair<long long,long long> > chn[N];
bool yes,yes1;
struct node
{
int a,b,upa,upb,ans;
};
vector <node> V[N];
int findpar(int x)
{
if (x==par[x])
return x;
return par[x]=findpar(par[x]);
}
void unun (int n1,int n2)
{
int x1=findpar(n1);
int x2=findpar(n2);
par[x2]=x1;
}
void dfs1 (int x,int p)
{
sz[x]=1;
par[x]=x;
sprs[x][0]=p;
lvl[x]=lvl[p]+1;
pair<int,long long> big={0,0};
for (int i=1;i<20;i++)
sprs[x][i]=sprs[sprs[x][i-1]][i-1];
for (int i=0;i<v[x].size();i++)
{
if (v[x][i]!=p)
{
dfs1(v[x][i],x);
sz[x]+=sz[v[x][i]];
big=max(big,make_pair(sz[v[x][i]],v[x][i]));
}
}
if (big.first)
unun(x,big.second);
}
int query (int x,int idx)
{
int ans=0;
int low=0,high=chn[x].size()-1,mid,idx1,idx2;
while (low<=high)
{
mid= (low+high)/2;
if (chn[x][mid].first>l)
low=mid+1;
else
{
idx1=mid;
high=mid-1;
}
}
low=0,high=chn[x].size()-1;
while (low<=high)
{
mid= (low+high)/2;
if (chn[x][mid].first<r)
high=mid-1;
else
{
idx2=mid;
low=mid+1;
}
}
ans=pfx[x][idx][idx2];
idx1--;
if (idx1>=0)
ans-=pfx[x][idx][idx1];
if (chn[x].back().first>r)
{
ans+= query(findpar(sprs[x][0]),idx);
}
return ans;
}
void dfs (int x,int p)
{
for (int i=0;i<v[x].size();i++)
{
if (v[x][i]!=p)
{
dfs(v[x][i],x);
dpsons[x]+=dp[v[x][i]];
}
}
dp[x]=dpsons[x];
int maxx=dpsons[x];
for (int i=0;i<V[x].size();i++)
{
int cur=dpsons[x];
cur-= dp[V[x][i].upa];
cur-= dp[V[x][i].upb];
cur+= dpsons[V[x][i].a];
cur+= dpsons[V[x][i].b];
int A= V[x][i].a;
int B= V[x][i].b;
if (x!=V[x][i].a&&sprs[V[x][i].a][0]!=x)
{
V[x][i].a=sprs[V[x][i].a][0];
l= lvl[V[x][i].a];
r= lvl[x]+1;
cur+= query(findpar(V[x][i].a),0);
r++;
cur-= dp[A];
if (l>=r)
cur-= (query(findpar(V[x][i].a),1));
}
if (x!=V[x][i].b&&sprs[V[x][i].b][0]!=x)
{
V[x][i].b=sprs[V[x][i].b][0];
l= lvl[V[x][i].b];
r= lvl[x]+1;
cur+= query(findpar(V[x][i].b),0);
r++;
cur-= dp[B];
if (l>=r)
{
cur-= (query(findpar(V[x][i].b),1));
}
}
cur+= V[x][i].ans;
maxx=max(maxx,cur);
}
dp[x]=maxx;
int idx=findpar(x);
pair<int,int> P= {lvl[x],x};
int o;
if (!chn[idx].empty())
o=chn[idx].back().second;
chn[idx].push_back(P);
if (pfx[idx][0].empty())
{
pfx[idx][0].push_back(dpsons[x]);
pfx[idx][1].push_back(dp[x]);
}
else
{
pfx[idx][0].push_back(pfx[idx][0].back());
pfx[idx][0].back()+= dpsons[x];
pfx[idx][1].push_back(pfx[idx][1].back());
pfx[idx][1].back()+= dp[x];
}
}
pair<int,int> lca(int x,int y)
{
pair<int,int> p;
if (lvl[x]<lvl[y])
swap(x,y);
for (int i=19;i>=0;i--)
{
if (lvl[sprs[x][i]]>lvl[y])
x=sprs[x][i];
}
if (sprs[x][0]==y)
{
p={x,y};
return p;
}
if (lvl[x]!=lvl[y])
x=sprs[x][0];
for (int i=19;i>=0;i--)
{
if (sprs[x][i]!=sprs[y][i])
{
x=sprs[x][i];
y=sprs[y][i];
}
}
p={x,y};
return p;
}
int main()
{
int maxx=0;
cin >>n;
for (int i=0;i<n-1;i++)
{
int a,b;
cin >>a>>b;
v[a].push_back(b);
v[b].push_back(a);
}
int st=1;
dfs1(st,0);
cin >>q;
while(q--)
{
int x,y,z;
cin >>x>>y>>z;
pair<int,int> p=lca(x,y);
int lc= sprs[p.first][0];
int val=z;
node A= {x,y,p.first,p.second,val};
maxx=max(maxx,z);
V[lc].push_back(A);
}
dfs(st,0);
cout <<dp[st];
return 0;
}
/*
7
3 4
6 5
2 7
1 5
7 5
4 5
5
4 3 10
5 6 5
2 6 9
7 2 2
1 3 8
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
5
7 5 4
5 8 9
4 3 9
1 3 3
2 8 11
20
17 10
11 4
8 3
3 16
1 14
15 18
5 4
6 18
10 18
19 4
16 7
2 13
4 12
12 20
9 20
18 13
20 14
14 7
13 7
15
19 9 2341
13 8 6974
8 3 3339
15 17 6515
10 13 4370
1 7 8376
18 2 9272
6 7 4595
1 20 505
10 9 308
6 19 8937
2 15 5072
5 4 4217
2 4 4170
19 12 8204
*/
Compilation message
election_campaign.cpp: In function 'void dfs1(int, int)':
election_campaign.cpp:34:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i=0;i<v[x].size();i++)
| ~^~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i=0;i<v[x].size();i++)
| ~^~~~~~~~~~~~
election_campaign.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i=0;i<V[x].size();i++)
| ~^~~~~~~~~~~~
election_campaign.cpp:135:9: warning: variable 'o' set but not used [-Wunused-but-set-variable]
135 | int o;
| ^
election_campaign.cpp: In function 'int query(int, int)':
election_campaign.cpp:74:9: warning: 'idx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
74 | idx1--;
| ~~~~^~
election_campaign.cpp:73:25: warning: 'idx2' may be used uninitialized in this function [-Wmaybe-uninitialized]
73 | ans=pfx[x][idx][idx2];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
7 ms |
12032 KB |
Output is correct |
4 |
Correct |
10 ms |
12340 KB |
Output is correct |
5 |
Incorrect |
253 ms |
31992 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
9 ms |
12416 KB |
Output is correct |
4 |
Correct |
431 ms |
48356 KB |
Output is correct |
5 |
Correct |
429 ms |
48248 KB |
Output is correct |
6 |
Correct |
397 ms |
48228 KB |
Output is correct |
7 |
Correct |
427 ms |
48228 KB |
Output is correct |
8 |
Correct |
428 ms |
48228 KB |
Output is correct |
9 |
Correct |
380 ms |
48280 KB |
Output is correct |
10 |
Correct |
426 ms |
48232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
9 ms |
12416 KB |
Output is correct |
4 |
Correct |
431 ms |
48356 KB |
Output is correct |
5 |
Correct |
429 ms |
48248 KB |
Output is correct |
6 |
Correct |
397 ms |
48228 KB |
Output is correct |
7 |
Correct |
427 ms |
48228 KB |
Output is correct |
8 |
Correct |
428 ms |
48228 KB |
Output is correct |
9 |
Correct |
380 ms |
48280 KB |
Output is correct |
10 |
Correct |
426 ms |
48232 KB |
Output is correct |
11 |
Correct |
50 ms |
13180 KB |
Output is correct |
12 |
Correct |
446 ms |
48228 KB |
Output is correct |
13 |
Correct |
449 ms |
48348 KB |
Output is correct |
14 |
Correct |
400 ms |
48232 KB |
Output is correct |
15 |
Correct |
445 ms |
48232 KB |
Output is correct |
16 |
Correct |
410 ms |
48300 KB |
Output is correct |
17 |
Correct |
448 ms |
48292 KB |
Output is correct |
18 |
Correct |
444 ms |
48228 KB |
Output is correct |
19 |
Correct |
402 ms |
48228 KB |
Output is correct |
20 |
Correct |
443 ms |
48228 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
601 ms |
34184 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
7 ms |
12032 KB |
Output is correct |
4 |
Correct |
10 ms |
12340 KB |
Output is correct |
5 |
Incorrect |
253 ms |
31992 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
12032 KB |
Output is correct |
2 |
Correct |
8 ms |
12032 KB |
Output is correct |
3 |
Correct |
7 ms |
12032 KB |
Output is correct |
4 |
Correct |
10 ms |
12340 KB |
Output is correct |
5 |
Incorrect |
253 ms |
31992 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |