#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
int n;
vector<int> adj[mxn];
int level[mxn] = {};
int pa[18][mxn] = {};
int in[mxn] = {};
int T = 0;
int out[mxn];
int q;
vector<tuple<int,int,int>> con[mxn];
void dfs0(int u,int prev) {
level[u] = level[prev]+1;
pa[0][u] = prev;
for(int i = 1; i < 18; i++) pa[i][u] = pa[i - 1][pa[i - 1][u]];
for(int v : adj[u]) {
if(v == prev) continue;
dfs0(v,u);
}
}
int findLCA(int u,int v) {
if(level[u] < level[v]) swap(u,v);
int diff = level[u] - level[v];
for(int i = 0;i < 18;i++) if((diff>>i)&1) u = pa[i][u];
if(u == v) return u;
for(int i = 17; i >= 0; i--) {
if(pa[i][u] != pa[i][v]){
u = pa[i][u];
v = pa[i][v];
}
}
return pa[0][u];
}
ll dp[mxn] = {};
ll child_sum[mxn] = {};
ll tot[18][mxn];
ll TOT(int i, int x) {
if(tot[i][x] != -1) return tot[i][x];
return TOT(i - 1, x) + TOT(i - 1, pa[i - 1][x]);
}
ll get(int x, int dif) {
ll sum = 0;
for(int i = 17; i >= 0; i--) {
if((dif >> i) & 1) {
sum += TOT(i, x);
x = pa[i][x];
}
}
return sum;
}
void dfs(int u, int prev) {
for(int v : adj[u]) {
if(v == prev) continue;
dfs(v, u);
child_sum[u] += dp[v];
}
dp[u] = child_sum[u];
for(auto [a, b, c] : con[u]) {
dp[u] = max(dp[u], get(a, level[a] - level[u]) + get(b, level[b] - level[u]) + c + child_sum[u]);
}
tot[0][u] = child_sum[u] - dp[u];
}
int main() {
cin >> n;
for(int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs0(1, 0);
memset(tot, -1, sizeof tot);
cin >> q;
for(int i = 1; i <= q; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
con[findLCA(a, b)].push_back({a, b, c});
}
dfs(1, 0);
cout<<dp[1]<<endl;
}
Compilation message
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d%d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~
election_campaign.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%d%d%d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19156 KB |
Output is correct |
2 |
Correct |
9 ms |
19184 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19320 KB |
Output is correct |
5 |
Correct |
87 ms |
31352 KB |
Output is correct |
6 |
Correct |
51 ms |
40164 KB |
Output is correct |
7 |
Correct |
80 ms |
37436 KB |
Output is correct |
8 |
Correct |
69 ms |
32048 KB |
Output is correct |
9 |
Correct |
86 ms |
35824 KB |
Output is correct |
10 |
Correct |
70 ms |
32072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
19156 KB |
Output is correct |
2 |
Incorrect |
10 ms |
19104 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
19156 KB |
Output is correct |
2 |
Incorrect |
10 ms |
19104 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
190 ms |
66392 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19156 KB |
Output is correct |
2 |
Correct |
9 ms |
19184 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19320 KB |
Output is correct |
5 |
Correct |
87 ms |
31352 KB |
Output is correct |
6 |
Correct |
51 ms |
40164 KB |
Output is correct |
7 |
Correct |
80 ms |
37436 KB |
Output is correct |
8 |
Correct |
69 ms |
32048 KB |
Output is correct |
9 |
Correct |
86 ms |
35824 KB |
Output is correct |
10 |
Correct |
70 ms |
32072 KB |
Output is correct |
11 |
Correct |
9 ms |
19284 KB |
Output is correct |
12 |
Correct |
12 ms |
19412 KB |
Output is correct |
13 |
Incorrect |
11 ms |
19412 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19156 KB |
Output is correct |
2 |
Correct |
9 ms |
19184 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19320 KB |
Output is correct |
5 |
Correct |
87 ms |
31352 KB |
Output is correct |
6 |
Correct |
51 ms |
40164 KB |
Output is correct |
7 |
Correct |
80 ms |
37436 KB |
Output is correct |
8 |
Correct |
69 ms |
32048 KB |
Output is correct |
9 |
Correct |
86 ms |
35824 KB |
Output is correct |
10 |
Correct |
70 ms |
32072 KB |
Output is correct |
11 |
Correct |
9 ms |
19156 KB |
Output is correct |
12 |
Incorrect |
10 ms |
19104 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |