#include <bits/stdc++.h>
using namespace std;
const int O = 2e5 + 5;
const int N = (1 << 10) + 5;
const int mod = 1e9 + 7; //998244353;
const int inf = 1e9;
int pr[] = {167772161, 469762049, 754974721, 1045430273, 1051721729, 1053818881};
int n, m, Time, a[O], b[O], c[O], h[O], in[O], out[O], f[21][O], dp[2][O];
vector <int> g[O], q[O];
int tree[O * 4];
void Update(int id, int l, int r, int u, int val){
if (l > u || r < u) return;
if (l == r){
tree[id] += val;
return;
}
int mid = (l + r) / 2;
Update(id << 1, l, mid, u, val);
Update(id << 1 | 1, mid + 1, r, u, val);
tree[id] = tree[id << 1] + tree[id << 1 | 1];
}
int Get(int id, int l, int r, int u, int v){
if (l > v || r < u) return 0;
if (u <= l && r <= v) return tree[id];
int mid = (l + r) / 2;
return Get(id << 1, l, mid, u, v) + Get(id << 1 | 1, mid + 1, r, u, v);
}
void init(int u, int par = 0){
in[u] = ++ Time;
for (int v : g[u]){
if (v != par){
h[v] = h[u] + 1;
f[0][v] = u;
init(v, u);
}
}
out[u] = ++ Time;
}
int Lca(int u, int v){
if (h[u] < h[v]) swap(u, v);
for (int i = 20; i >= 0; -- i){
if (h[u] - (1 << i) >= h[v]) u = f[i][u];
}
if (u == v) return u;
for (int i = 20; i >= 0; -- i){
if (f[i][u] != f[i][v]){
u = f[i][u];
v = f[i][v];
}
}
return f[0][u];
}
int Jump(int u, int d){
for (int i = 20; i >= 0; -- i){
if (d >> i & 1) u = f[i][u];
}
return u;
}
void dfs(int u, int par = 0){
dp[0][u] = dp[1][u] = 0;
for (int v : g[u]){
if (v != par){
dfs(v, u);
dp[0][u] += max(dp[1][v], dp[0][v]);
}
}
for (int i : q[u]){
int x = (a[i] == u) ? -1 : a[i];
int y = (b[i] == u) ? -1 : b[i];
int val = dp[0][u] + c[i];
if (x != -1){
val = val + Get(1, 1, Time, in[u], in[x]);
}
if (y != -1){
val = val + Get(1, 1, Time, in[u], in[y]);
}
dp[1][u] = max(dp[1][u], val);
}
Update(1, 1, Time, in[u], dp[0][u] - max(dp[0][u], dp[1][u]));
Update(1, 1, Time, out[u], max(dp[0][u], dp[1][u]) - dp[0][u]);
}
main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i < n; ++ i){
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
memset(f, -1, sizeof(f));
init(1);
for (int i = 1; i <= 20; ++ i){
for (int j = 1; j <= n; ++ j){
if (f[i - 1][j] != -1) f[i][j] = f[i - 1][f[i - 1][j]];
}
}
cin >> m;
for (int i = 1; i <= m; ++ i){
cin >> a[i] >> b[i] >> c[i];
int u = Lca(a[i], b[i]);
q[u].push_back(i);
}
dfs(1);
cout << max(dp[0][1], dp[1][1]);
}
/**
1
6 3
1 2 1 4 3 8
**/
Compilation message
election_campaign.cpp:102:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
102 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
29020 KB |
Output is correct |
2 |
Correct |
5 ms |
28764 KB |
Output is correct |
3 |
Correct |
4 ms |
28764 KB |
Output is correct |
4 |
Correct |
4 ms |
29276 KB |
Output is correct |
5 |
Correct |
70 ms |
36380 KB |
Output is correct |
6 |
Correct |
53 ms |
43860 KB |
Output is correct |
7 |
Correct |
61 ms |
41300 KB |
Output is correct |
8 |
Correct |
50 ms |
36676 KB |
Output is correct |
9 |
Correct |
55 ms |
39764 KB |
Output is correct |
10 |
Correct |
52 ms |
36692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
28764 KB |
Output is correct |
2 |
Correct |
4 ms |
28764 KB |
Output is correct |
3 |
Correct |
5 ms |
28764 KB |
Output is correct |
4 |
Correct |
120 ms |
47516 KB |
Output is correct |
5 |
Correct |
120 ms |
47696 KB |
Output is correct |
6 |
Correct |
97 ms |
47592 KB |
Output is correct |
7 |
Correct |
119 ms |
47444 KB |
Output is correct |
8 |
Correct |
126 ms |
47640 KB |
Output is correct |
9 |
Correct |
98 ms |
47700 KB |
Output is correct |
10 |
Correct |
117 ms |
47444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
28764 KB |
Output is correct |
2 |
Correct |
4 ms |
28764 KB |
Output is correct |
3 |
Correct |
5 ms |
28764 KB |
Output is correct |
4 |
Correct |
120 ms |
47516 KB |
Output is correct |
5 |
Correct |
120 ms |
47696 KB |
Output is correct |
6 |
Correct |
97 ms |
47592 KB |
Output is correct |
7 |
Correct |
119 ms |
47444 KB |
Output is correct |
8 |
Correct |
126 ms |
47640 KB |
Output is correct |
9 |
Correct |
98 ms |
47700 KB |
Output is correct |
10 |
Correct |
117 ms |
47444 KB |
Output is correct |
11 |
Correct |
13 ms |
29532 KB |
Output is correct |
12 |
Correct |
120 ms |
47772 KB |
Output is correct |
13 |
Correct |
112 ms |
47884 KB |
Output is correct |
14 |
Correct |
95 ms |
47956 KB |
Output is correct |
15 |
Correct |
129 ms |
47956 KB |
Output is correct |
16 |
Correct |
96 ms |
48940 KB |
Output is correct |
17 |
Correct |
111 ms |
47956 KB |
Output is correct |
18 |
Correct |
115 ms |
47916 KB |
Output is correct |
19 |
Correct |
97 ms |
47956 KB |
Output is correct |
20 |
Correct |
105 ms |
48896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
39416 KB |
Output is correct |
2 |
Correct |
98 ms |
47700 KB |
Output is correct |
3 |
Correct |
155 ms |
44628 KB |
Output is correct |
4 |
Correct |
123 ms |
39632 KB |
Output is correct |
5 |
Correct |
112 ms |
45396 KB |
Output is correct |
6 |
Correct |
116 ms |
39888 KB |
Output is correct |
7 |
Correct |
142 ms |
43788 KB |
Output is correct |
8 |
Correct |
100 ms |
39764 KB |
Output is correct |
9 |
Correct |
96 ms |
47568 KB |
Output is correct |
10 |
Correct |
142 ms |
42940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
29020 KB |
Output is correct |
2 |
Correct |
5 ms |
28764 KB |
Output is correct |
3 |
Correct |
4 ms |
28764 KB |
Output is correct |
4 |
Correct |
4 ms |
29276 KB |
Output is correct |
5 |
Correct |
70 ms |
36380 KB |
Output is correct |
6 |
Correct |
53 ms |
43860 KB |
Output is correct |
7 |
Correct |
61 ms |
41300 KB |
Output is correct |
8 |
Correct |
50 ms |
36676 KB |
Output is correct |
9 |
Correct |
55 ms |
39764 KB |
Output is correct |
10 |
Correct |
52 ms |
36692 KB |
Output is correct |
11 |
Correct |
5 ms |
29276 KB |
Output is correct |
12 |
Correct |
5 ms |
28932 KB |
Output is correct |
13 |
Correct |
5 ms |
29276 KB |
Output is correct |
14 |
Correct |
5 ms |
28764 KB |
Output is correct |
15 |
Correct |
5 ms |
28704 KB |
Output is correct |
16 |
Correct |
5 ms |
28764 KB |
Output is correct |
17 |
Correct |
5 ms |
28764 KB |
Output is correct |
18 |
Correct |
5 ms |
28868 KB |
Output is correct |
19 |
Correct |
6 ms |
28764 KB |
Output is correct |
20 |
Correct |
5 ms |
29276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
29020 KB |
Output is correct |
2 |
Correct |
5 ms |
28764 KB |
Output is correct |
3 |
Correct |
4 ms |
28764 KB |
Output is correct |
4 |
Correct |
4 ms |
29276 KB |
Output is correct |
5 |
Correct |
70 ms |
36380 KB |
Output is correct |
6 |
Correct |
53 ms |
43860 KB |
Output is correct |
7 |
Correct |
61 ms |
41300 KB |
Output is correct |
8 |
Correct |
50 ms |
36676 KB |
Output is correct |
9 |
Correct |
55 ms |
39764 KB |
Output is correct |
10 |
Correct |
52 ms |
36692 KB |
Output is correct |
11 |
Correct |
4 ms |
28764 KB |
Output is correct |
12 |
Correct |
4 ms |
28764 KB |
Output is correct |
13 |
Correct |
5 ms |
28764 KB |
Output is correct |
14 |
Correct |
120 ms |
47516 KB |
Output is correct |
15 |
Correct |
120 ms |
47696 KB |
Output is correct |
16 |
Correct |
97 ms |
47592 KB |
Output is correct |
17 |
Correct |
119 ms |
47444 KB |
Output is correct |
18 |
Correct |
126 ms |
47640 KB |
Output is correct |
19 |
Correct |
98 ms |
47700 KB |
Output is correct |
20 |
Correct |
117 ms |
47444 KB |
Output is correct |
21 |
Correct |
13 ms |
29532 KB |
Output is correct |
22 |
Correct |
120 ms |
47772 KB |
Output is correct |
23 |
Correct |
112 ms |
47884 KB |
Output is correct |
24 |
Correct |
95 ms |
47956 KB |
Output is correct |
25 |
Correct |
129 ms |
47956 KB |
Output is correct |
26 |
Correct |
96 ms |
48940 KB |
Output is correct |
27 |
Correct |
111 ms |
47956 KB |
Output is correct |
28 |
Correct |
115 ms |
47916 KB |
Output is correct |
29 |
Correct |
97 ms |
47956 KB |
Output is correct |
30 |
Correct |
105 ms |
48896 KB |
Output is correct |
31 |
Correct |
133 ms |
39416 KB |
Output is correct |
32 |
Correct |
98 ms |
47700 KB |
Output is correct |
33 |
Correct |
155 ms |
44628 KB |
Output is correct |
34 |
Correct |
123 ms |
39632 KB |
Output is correct |
35 |
Correct |
112 ms |
45396 KB |
Output is correct |
36 |
Correct |
116 ms |
39888 KB |
Output is correct |
37 |
Correct |
142 ms |
43788 KB |
Output is correct |
38 |
Correct |
100 ms |
39764 KB |
Output is correct |
39 |
Correct |
96 ms |
47568 KB |
Output is correct |
40 |
Correct |
142 ms |
42940 KB |
Output is correct |
41 |
Correct |
5 ms |
29276 KB |
Output is correct |
42 |
Correct |
5 ms |
28932 KB |
Output is correct |
43 |
Correct |
5 ms |
29276 KB |
Output is correct |
44 |
Correct |
5 ms |
28764 KB |
Output is correct |
45 |
Correct |
5 ms |
28704 KB |
Output is correct |
46 |
Correct |
5 ms |
28764 KB |
Output is correct |
47 |
Correct |
5 ms |
28764 KB |
Output is correct |
48 |
Correct |
5 ms |
28868 KB |
Output is correct |
49 |
Correct |
6 ms |
28764 KB |
Output is correct |
50 |
Correct |
5 ms |
29276 KB |
Output is correct |
51 |
Correct |
112 ms |
40016 KB |
Output is correct |
52 |
Correct |
125 ms |
47700 KB |
Output is correct |
53 |
Correct |
156 ms |
43216 KB |
Output is correct |
54 |
Correct |
102 ms |
40020 KB |
Output is correct |
55 |
Correct |
130 ms |
39892 KB |
Output is correct |
56 |
Correct |
122 ms |
47956 KB |
Output is correct |
57 |
Correct |
123 ms |
44092 KB |
Output is correct |
58 |
Correct |
118 ms |
40020 KB |
Output is correct |
59 |
Correct |
100 ms |
40016 KB |
Output is correct |
60 |
Correct |
113 ms |
47956 KB |
Output is correct |
61 |
Correct |
118 ms |
44020 KB |
Output is correct |
62 |
Correct |
127 ms |
39984 KB |
Output is correct |
63 |
Correct |
133 ms |
41932 KB |
Output is correct |
64 |
Correct |
116 ms |
47836 KB |
Output is correct |
65 |
Correct |
146 ms |
43884 KB |
Output is correct |
66 |
Correct |
104 ms |
40184 KB |
Output is correct |
67 |
Correct |
124 ms |
39880 KB |
Output is correct |
68 |
Correct |
121 ms |
47956 KB |
Output is correct |
69 |
Correct |
131 ms |
42840 KB |
Output is correct |
70 |
Correct |
136 ms |
40068 KB |
Output is correct |