#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define F first
#define S second
const int MN = 1e5+5;
int N, M, i, x, y, w, f[MN], g[MN], sz[MN], vis[MN][2], st[3*MN], lnk[MN], par[MN], nxt;
vi adj[MN]; pii big[MN];
struct plan{int x, y, w;};
vector<plan> vec[MN];
void dfs(int n,int p){
vis[n][0] = ++nxt;
par[n] = p; sz[n] = 1;
big[n] = {-1, -1};
for(auto v : adj[n]){
if(v==p) continue;
dfs(v, n);
sz[n] += sz[v];
if(sz[v]>big[n].F) big[n]={sz[v],v};
}
vis[n][1] = nxt;
if(big[n].S!=-1) lnk[big[n].S]=n;
}
void dfs2(int n,int p){
if(!lnk[n]) lnk[n] = n;
else lnk[n] = lnk[lnk[n]];
for(auto v : adj[n]){
if(v==p) continue;
dfs2(v, n);
}
}
inline bool con(int x,int y){return vis[x][0]<=vis[y][0]&&vis[y][1]<=vis[x][1];}
inline int lca(int x,int y){
while(!con(lnk[x],y)) x=par[lnk[x]];
while(!con(lnk[y],x)) y=par[lnk[y]];
return con(x,y)?x:y;
}
void upd(int i,int s,int e,int ss,int se,int val){
if(s>=ss&&e<=se) st[i] += val;
else if((s+e)/2<ss) upd(2*i+1,(s+e)/2+1,e,ss,se,val);
else if((s+e)/2>=se) upd(2*i,s,(s+e)/2,ss,se,val);
else upd(2*i,s,(s+e)/2,ss,se,val), upd(2*i+1,(s+e)/2+1,e,ss,se,val);
}
int qu(int i,int s,int e,int idx){
if(s^e){
if((s+e)/2<idx) return st[i]+qu(2*i+1,(s+e)/2+1,e,idx);
else return st[i]+qu(2*i,s,(s+e)/2,idx);
}
else return st[i];
}
void solve(int n,int p){
for(auto v : adj[n]){
if(v==p) continue;
solve(v, n);
g[n] += max(g[v],f[v]);
}
for(auto v : vec[n])
f[n] = max(f[n],qu(1,1,N,vis[v.x][0])+qu(1,1,N,vis[v.y][0])+g[n]+v.w);
f[n] = max(f[n], g[n]);
upd(1,1,N,vis[n][0],vis[n][1],g[n]-f[n]);
}
int main(){
scanf("%d",&N);
for(i=1;i<N;i++){
scanf("%d%d",&x,&y);
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1,0);
dfs2(1,0);
scanf("%d",&M);
for(i=1;i<=M;i++){
scanf("%d%d%d",&x,&y,&w);
int l = lca(x, y);
vec[l].push_back({x,y,w});
}
solve(1,0);
printf("%d\n",f[1]);
return 0;
}
Compilation message
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
election_campaign.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%d%d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~
election_campaign.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%d",&M);
| ~~~~~^~~~~~~~~
election_campaign.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | scanf("%d%d%d",&x,&y,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
135 ms |
14072 KB |
Output is correct |
6 |
Correct |
76 ms |
23288 KB |
Output is correct |
7 |
Correct |
102 ms |
19960 KB |
Output is correct |
8 |
Correct |
81 ms |
13816 KB |
Output is correct |
9 |
Correct |
103 ms |
18072 KB |
Output is correct |
10 |
Correct |
82 ms |
13816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
5152 KB |
Output is correct |
3 |
Correct |
4 ms |
5248 KB |
Output is correct |
4 |
Correct |
130 ms |
26616 KB |
Output is correct |
5 |
Correct |
130 ms |
26616 KB |
Output is correct |
6 |
Correct |
126 ms |
26616 KB |
Output is correct |
7 |
Correct |
133 ms |
26616 KB |
Output is correct |
8 |
Correct |
129 ms |
26616 KB |
Output is correct |
9 |
Correct |
131 ms |
26616 KB |
Output is correct |
10 |
Correct |
129 ms |
26492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
5152 KB |
Output is correct |
3 |
Correct |
4 ms |
5248 KB |
Output is correct |
4 |
Correct |
130 ms |
26616 KB |
Output is correct |
5 |
Correct |
130 ms |
26616 KB |
Output is correct |
6 |
Correct |
126 ms |
26616 KB |
Output is correct |
7 |
Correct |
133 ms |
26616 KB |
Output is correct |
8 |
Correct |
129 ms |
26616 KB |
Output is correct |
9 |
Correct |
131 ms |
26616 KB |
Output is correct |
10 |
Correct |
129 ms |
26492 KB |
Output is correct |
11 |
Correct |
19 ms |
6016 KB |
Output is correct |
12 |
Correct |
137 ms |
26872 KB |
Output is correct |
13 |
Correct |
137 ms |
26872 KB |
Output is correct |
14 |
Correct |
129 ms |
26872 KB |
Output is correct |
15 |
Correct |
141 ms |
26784 KB |
Output is correct |
16 |
Correct |
129 ms |
26872 KB |
Output is correct |
17 |
Correct |
134 ms |
26872 KB |
Output is correct |
18 |
Correct |
143 ms |
26876 KB |
Output is correct |
19 |
Correct |
131 ms |
26888 KB |
Output is correct |
20 |
Correct |
135 ms |
26872 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
201 ms |
16816 KB |
Output is correct |
2 |
Correct |
127 ms |
26616 KB |
Output is correct |
3 |
Correct |
181 ms |
23036 KB |
Output is correct |
4 |
Correct |
156 ms |
16688 KB |
Output is correct |
5 |
Correct |
181 ms |
22264 KB |
Output is correct |
6 |
Correct |
157 ms |
16748 KB |
Output is correct |
7 |
Correct |
184 ms |
21940 KB |
Output is correct |
8 |
Correct |
228 ms |
17144 KB |
Output is correct |
9 |
Correct |
130 ms |
26616 KB |
Output is correct |
10 |
Correct |
175 ms |
20788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
135 ms |
14072 KB |
Output is correct |
6 |
Correct |
76 ms |
23288 KB |
Output is correct |
7 |
Correct |
102 ms |
19960 KB |
Output is correct |
8 |
Correct |
81 ms |
13816 KB |
Output is correct |
9 |
Correct |
103 ms |
18072 KB |
Output is correct |
10 |
Correct |
82 ms |
13816 KB |
Output is correct |
11 |
Correct |
5 ms |
5120 KB |
Output is correct |
12 |
Correct |
5 ms |
5248 KB |
Output is correct |
13 |
Correct |
5 ms |
5248 KB |
Output is correct |
14 |
Correct |
5 ms |
5248 KB |
Output is correct |
15 |
Correct |
5 ms |
5120 KB |
Output is correct |
16 |
Correct |
5 ms |
5248 KB |
Output is correct |
17 |
Correct |
5 ms |
5120 KB |
Output is correct |
18 |
Correct |
5 ms |
5248 KB |
Output is correct |
19 |
Correct |
5 ms |
5120 KB |
Output is correct |
20 |
Correct |
5 ms |
5248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
4992 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
135 ms |
14072 KB |
Output is correct |
6 |
Correct |
76 ms |
23288 KB |
Output is correct |
7 |
Correct |
102 ms |
19960 KB |
Output is correct |
8 |
Correct |
81 ms |
13816 KB |
Output is correct |
9 |
Correct |
103 ms |
18072 KB |
Output is correct |
10 |
Correct |
82 ms |
13816 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
4 ms |
5152 KB |
Output is correct |
13 |
Correct |
4 ms |
5248 KB |
Output is correct |
14 |
Correct |
130 ms |
26616 KB |
Output is correct |
15 |
Correct |
130 ms |
26616 KB |
Output is correct |
16 |
Correct |
126 ms |
26616 KB |
Output is correct |
17 |
Correct |
133 ms |
26616 KB |
Output is correct |
18 |
Correct |
129 ms |
26616 KB |
Output is correct |
19 |
Correct |
131 ms |
26616 KB |
Output is correct |
20 |
Correct |
129 ms |
26492 KB |
Output is correct |
21 |
Correct |
19 ms |
6016 KB |
Output is correct |
22 |
Correct |
137 ms |
26872 KB |
Output is correct |
23 |
Correct |
137 ms |
26872 KB |
Output is correct |
24 |
Correct |
129 ms |
26872 KB |
Output is correct |
25 |
Correct |
141 ms |
26784 KB |
Output is correct |
26 |
Correct |
129 ms |
26872 KB |
Output is correct |
27 |
Correct |
134 ms |
26872 KB |
Output is correct |
28 |
Correct |
143 ms |
26876 KB |
Output is correct |
29 |
Correct |
131 ms |
26888 KB |
Output is correct |
30 |
Correct |
135 ms |
26872 KB |
Output is correct |
31 |
Correct |
201 ms |
16816 KB |
Output is correct |
32 |
Correct |
127 ms |
26616 KB |
Output is correct |
33 |
Correct |
181 ms |
23036 KB |
Output is correct |
34 |
Correct |
156 ms |
16688 KB |
Output is correct |
35 |
Correct |
181 ms |
22264 KB |
Output is correct |
36 |
Correct |
157 ms |
16748 KB |
Output is correct |
37 |
Correct |
184 ms |
21940 KB |
Output is correct |
38 |
Correct |
228 ms |
17144 KB |
Output is correct |
39 |
Correct |
130 ms |
26616 KB |
Output is correct |
40 |
Correct |
175 ms |
20788 KB |
Output is correct |
41 |
Correct |
5 ms |
5120 KB |
Output is correct |
42 |
Correct |
5 ms |
5248 KB |
Output is correct |
43 |
Correct |
5 ms |
5248 KB |
Output is correct |
44 |
Correct |
5 ms |
5248 KB |
Output is correct |
45 |
Correct |
5 ms |
5120 KB |
Output is correct |
46 |
Correct |
5 ms |
5248 KB |
Output is correct |
47 |
Correct |
5 ms |
5120 KB |
Output is correct |
48 |
Correct |
5 ms |
5248 KB |
Output is correct |
49 |
Correct |
5 ms |
5120 KB |
Output is correct |
50 |
Correct |
5 ms |
5248 KB |
Output is correct |
51 |
Correct |
216 ms |
17528 KB |
Output is correct |
52 |
Correct |
135 ms |
26872 KB |
Output is correct |
53 |
Correct |
181 ms |
21228 KB |
Output is correct |
54 |
Correct |
149 ms |
17076 KB |
Output is correct |
55 |
Correct |
220 ms |
17200 KB |
Output is correct |
56 |
Correct |
133 ms |
26872 KB |
Output is correct |
57 |
Correct |
191 ms |
22032 KB |
Output is correct |
58 |
Correct |
153 ms |
16940 KB |
Output is correct |
59 |
Correct |
209 ms |
17400 KB |
Output is correct |
60 |
Correct |
152 ms |
26872 KB |
Output is correct |
61 |
Correct |
181 ms |
22136 KB |
Output is correct |
62 |
Correct |
153 ms |
16716 KB |
Output is correct |
63 |
Correct |
204 ms |
16868 KB |
Output is correct |
64 |
Correct |
134 ms |
26872 KB |
Output is correct |
65 |
Correct |
186 ms |
21936 KB |
Output is correct |
66 |
Correct |
154 ms |
17076 KB |
Output is correct |
67 |
Correct |
214 ms |
17052 KB |
Output is correct |
68 |
Correct |
141 ms |
26872 KB |
Output is correct |
69 |
Correct |
182 ms |
20600 KB |
Output is correct |
70 |
Correct |
151 ms |
17116 KB |
Output is correct |