#include <bits/stdc++.h>
#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 10007
#define left lleft
#define right rright
#define INF 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus
using namespace std;
int N,M,nn;
int seg[300000];
int d[100002],sum[100002];
int rs[100002],re[100002];
int par[100002][20],lev[100002];
bool check[100002];
vector<int> edge[100002],calc[100002];
struct data{
int x,y,z;
}a[100002];
int dfscnt;
void setting(int x){
rs[x] = ++dfscnt;
check[x] = true;
for(auto &i : edge[x]){
if(check[i]) continue;
par[i][0] = x;
for(int j=1; j<=18; j++) par[i][j] = par[par[i][j-1]][j-1];
lev[i] = lev[x]+1;
setting(i);
}
re[x] = dfscnt;
}
int getlca(int x,int y){
if(lev[x] > lev[y]) swap(x,y);
for(int i=0; i<=18; i++){
if(((lev[y]-lev[x])&(1<<i)) == 0) continue;
y = par[y][i];
}
if(x == y) return x;
int t;
for(int i=0; ; i++){
if(par[x][i] == par[y][i]){
t = i;
break;
}
}
while(t){
t--;
if(par[x][t] != par[y][t]){
x = par[x][t];
y = par[y][t];
}
}
return par[x][0];
}
void update(int node,int l,int r,int s,int e,int value){
if(r < s || e < l) return;
if(s <= l && r <= e){
seg[node] += value;
return;
}
int mid = (l+r)/2;
update(node*2,l,mid,s,e,value);
update(node*2+1,mid+1,r,s,e,value);
}
int get(int x){
int tsum = 0;
x = nn-1+rs[x];
while(x){
tsum += seg[x];
x /= 2;
}
return tsum;
}
void dfs(int x){
vector<int> tmp;
check[x] = true;
for(auto &i : edge[x]){
if(check[i]) continue;
dfs(i);
d[x] += d[i];
tmp.pb(i);
}
sum[x] = d[x];
for(auto &i : tmp){
update(1,1,nn,rs[i],re[i],d[i]-sum[i]);
}
for(auto &i : calc[x]){
int tx,ty,tz;
tx = a[i].x; ty = a[i].y; tz = a[i].z;
d[x] = max(d[x],sum[x]-get(tx)-get(ty)+tz);
}
}
int main(){
scanf("%d",&N);
for(nn=1; nn<N; nn*=2);
for(int i=1; i<N; i++){
int x,y;
scanf("%d %d",&x,&y);
edge[x].pb(y);
edge[y].pb(x);
}
setting(1);
scanf("%d",&M);
for(int i=1; i<=M; i++){
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z);
int lca = getlca(a[i].x,a[i].y);
calc[lca].pb(i);
}
for(int i=1; i<=N; i++) check[i] = false;
dfs(1);
printf("%d\n",d[1]);
return 0;
}
Compilation message
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:103:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
election_campaign.cpp:107:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
^
election_campaign.cpp:112:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&M);
^
election_campaign.cpp:114:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
18916 KB |
Output is correct |
2 |
Correct |
3 ms |
18916 KB |
Output is correct |
3 |
Correct |
0 ms |
18916 KB |
Output is correct |
4 |
Correct |
3 ms |
18916 KB |
Output is correct |
5 |
Correct |
193 ms |
22216 KB |
Output is correct |
6 |
Correct |
106 ms |
29776 KB |
Output is correct |
7 |
Correct |
196 ms |
27076 KB |
Output is correct |
8 |
Correct |
123 ms |
22888 KB |
Output is correct |
9 |
Correct |
226 ms |
25788 KB |
Output is correct |
10 |
Correct |
119 ms |
22824 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
18916 KB |
Output is correct |
2 |
Correct |
0 ms |
18916 KB |
Output is correct |
3 |
Correct |
0 ms |
18916 KB |
Output is correct |
4 |
Correct |
229 ms |
30828 KB |
Output is correct |
5 |
Correct |
223 ms |
30824 KB |
Output is correct |
6 |
Correct |
216 ms |
30824 KB |
Output is correct |
7 |
Correct |
229 ms |
30824 KB |
Output is correct |
8 |
Correct |
286 ms |
30832 KB |
Output is correct |
9 |
Correct |
233 ms |
30828 KB |
Output is correct |
10 |
Correct |
243 ms |
30828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
18916 KB |
Output is correct |
2 |
Correct |
0 ms |
18916 KB |
Output is correct |
3 |
Correct |
0 ms |
18916 KB |
Output is correct |
4 |
Correct |
229 ms |
30828 KB |
Output is correct |
5 |
Correct |
223 ms |
30824 KB |
Output is correct |
6 |
Correct |
216 ms |
30824 KB |
Output is correct |
7 |
Correct |
229 ms |
30824 KB |
Output is correct |
8 |
Correct |
286 ms |
30832 KB |
Output is correct |
9 |
Correct |
233 ms |
30828 KB |
Output is correct |
10 |
Correct |
243 ms |
30828 KB |
Output is correct |
11 |
Correct |
13 ms |
19180 KB |
Output is correct |
12 |
Correct |
179 ms |
30832 KB |
Output is correct |
13 |
Correct |
173 ms |
30824 KB |
Output is correct |
14 |
Correct |
139 ms |
30832 KB |
Output is correct |
15 |
Correct |
216 ms |
30828 KB |
Output is correct |
16 |
Correct |
163 ms |
30828 KB |
Output is correct |
17 |
Correct |
256 ms |
30824 KB |
Output is correct |
18 |
Correct |
169 ms |
30828 KB |
Output is correct |
19 |
Correct |
219 ms |
30828 KB |
Output is correct |
20 |
Correct |
243 ms |
30828 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
256 ms |
22764 KB |
Output is correct |
2 |
Correct |
159 ms |
30828 KB |
Output is correct |
3 |
Correct |
413 ms |
28200 KB |
Output is correct |
4 |
Correct |
193 ms |
23392 KB |
Output is correct |
5 |
Correct |
373 ms |
27856 KB |
Output is correct |
6 |
Correct |
189 ms |
23576 KB |
Output is correct |
7 |
Correct |
393 ms |
27516 KB |
Output is correct |
8 |
Correct |
296 ms |
23164 KB |
Output is correct |
9 |
Correct |
203 ms |
30824 KB |
Output is correct |
10 |
Correct |
426 ms |
26376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
18916 KB |
Output is correct |
2 |
Correct |
3 ms |
18916 KB |
Output is correct |
3 |
Correct |
0 ms |
18916 KB |
Output is correct |
4 |
Correct |
3 ms |
18916 KB |
Output is correct |
5 |
Correct |
193 ms |
22216 KB |
Output is correct |
6 |
Correct |
106 ms |
29776 KB |
Output is correct |
7 |
Correct |
196 ms |
27076 KB |
Output is correct |
8 |
Correct |
123 ms |
22888 KB |
Output is correct |
9 |
Correct |
226 ms |
25788 KB |
Output is correct |
10 |
Correct |
119 ms |
22824 KB |
Output is correct |
11 |
Correct |
3 ms |
18916 KB |
Output is correct |
12 |
Correct |
0 ms |
18916 KB |
Output is correct |
13 |
Correct |
0 ms |
18916 KB |
Output is correct |
14 |
Correct |
0 ms |
18916 KB |
Output is correct |
15 |
Correct |
0 ms |
18916 KB |
Output is correct |
16 |
Correct |
3 ms |
18916 KB |
Output is correct |
17 |
Correct |
0 ms |
18916 KB |
Output is correct |
18 |
Correct |
0 ms |
18916 KB |
Output is correct |
19 |
Correct |
0 ms |
18916 KB |
Output is correct |
20 |
Correct |
6 ms |
18916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
18916 KB |
Output is correct |
2 |
Correct |
3 ms |
18916 KB |
Output is correct |
3 |
Correct |
0 ms |
18916 KB |
Output is correct |
4 |
Correct |
3 ms |
18916 KB |
Output is correct |
5 |
Correct |
193 ms |
22216 KB |
Output is correct |
6 |
Correct |
106 ms |
29776 KB |
Output is correct |
7 |
Correct |
196 ms |
27076 KB |
Output is correct |
8 |
Correct |
123 ms |
22888 KB |
Output is correct |
9 |
Correct |
226 ms |
25788 KB |
Output is correct |
10 |
Correct |
119 ms |
22824 KB |
Output is correct |
11 |
Correct |
3 ms |
18916 KB |
Output is correct |
12 |
Correct |
0 ms |
18916 KB |
Output is correct |
13 |
Correct |
0 ms |
18916 KB |
Output is correct |
14 |
Correct |
229 ms |
30828 KB |
Output is correct |
15 |
Correct |
223 ms |
30824 KB |
Output is correct |
16 |
Correct |
216 ms |
30824 KB |
Output is correct |
17 |
Correct |
229 ms |
30824 KB |
Output is correct |
18 |
Correct |
286 ms |
30832 KB |
Output is correct |
19 |
Correct |
233 ms |
30828 KB |
Output is correct |
20 |
Correct |
243 ms |
30828 KB |
Output is correct |
21 |
Correct |
13 ms |
19180 KB |
Output is correct |
22 |
Correct |
179 ms |
30832 KB |
Output is correct |
23 |
Correct |
173 ms |
30824 KB |
Output is correct |
24 |
Correct |
139 ms |
30832 KB |
Output is correct |
25 |
Correct |
216 ms |
30828 KB |
Output is correct |
26 |
Correct |
163 ms |
30828 KB |
Output is correct |
27 |
Correct |
256 ms |
30824 KB |
Output is correct |
28 |
Correct |
169 ms |
30828 KB |
Output is correct |
29 |
Correct |
219 ms |
30828 KB |
Output is correct |
30 |
Correct |
243 ms |
30828 KB |
Output is correct |
31 |
Correct |
256 ms |
22764 KB |
Output is correct |
32 |
Correct |
159 ms |
30828 KB |
Output is correct |
33 |
Correct |
413 ms |
28200 KB |
Output is correct |
34 |
Correct |
193 ms |
23392 KB |
Output is correct |
35 |
Correct |
373 ms |
27856 KB |
Output is correct |
36 |
Correct |
189 ms |
23576 KB |
Output is correct |
37 |
Correct |
393 ms |
27516 KB |
Output is correct |
38 |
Correct |
296 ms |
23164 KB |
Output is correct |
39 |
Correct |
203 ms |
30824 KB |
Output is correct |
40 |
Correct |
426 ms |
26376 KB |
Output is correct |
41 |
Correct |
3 ms |
18916 KB |
Output is correct |
42 |
Correct |
0 ms |
18916 KB |
Output is correct |
43 |
Correct |
0 ms |
18916 KB |
Output is correct |
44 |
Correct |
0 ms |
18916 KB |
Output is correct |
45 |
Correct |
0 ms |
18916 KB |
Output is correct |
46 |
Correct |
3 ms |
18916 KB |
Output is correct |
47 |
Correct |
0 ms |
18916 KB |
Output is correct |
48 |
Correct |
0 ms |
18916 KB |
Output is correct |
49 |
Correct |
0 ms |
18916 KB |
Output is correct |
50 |
Correct |
6 ms |
18916 KB |
Output is correct |
51 |
Correct |
329 ms |
23176 KB |
Output is correct |
52 |
Correct |
286 ms |
30832 KB |
Output is correct |
53 |
Correct |
403 ms |
26756 KB |
Output is correct |
54 |
Correct |
209 ms |
23380 KB |
Output is correct |
55 |
Correct |
266 ms |
22904 KB |
Output is correct |
56 |
Correct |
233 ms |
30828 KB |
Output is correct |
57 |
Correct |
363 ms |
27024 KB |
Output is correct |
58 |
Correct |
213 ms |
23280 KB |
Output is correct |
59 |
Correct |
316 ms |
23176 KB |
Output is correct |
60 |
Correct |
296 ms |
30824 KB |
Output is correct |
61 |
Correct |
433 ms |
27244 KB |
Output is correct |
62 |
Correct |
203 ms |
23528 KB |
Output is correct |
63 |
Correct |
339 ms |
22912 KB |
Output is correct |
64 |
Correct |
256 ms |
30828 KB |
Output is correct |
65 |
Correct |
413 ms |
27100 KB |
Output is correct |
66 |
Correct |
209 ms |
23360 KB |
Output is correct |
67 |
Correct |
293 ms |
23024 KB |
Output is correct |
68 |
Correct |
259 ms |
30828 KB |
Output is correct |
69 |
Correct |
333 ms |
26100 KB |
Output is correct |
70 |
Correct |
163 ms |
23532 KB |
Output is correct |