#include <bits/stdc++.h>
using namespace std;
const int N = (int)1e5 + 7;
vector <int> gr[N];
int n, m;
vector <tuple<int, int, int>> vec;
int tin[N], tout[N], lc[17][N], sz[N];
int tiktak;
vector <int> query[N];
void dfs(int v, int pr) {
tin[v] = ++tiktak;
lc[0][v] = pr;
for (int i = 1; i < 17; i++) {
lc[i][v] = lc[i - 1][lc[i - 1][v]];
}
sz[v] = 1;
for (int to : gr[v]) {
if (to == pr) continue;
dfs(to, v);
sz[v] += sz[to];
}
tout[v] = ++tiktak;
}
bool upper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a, int b) {
if (upper(a, b)) return a;
if (upper(b, a)) return b;
for (int i = 16; i >= 0; i--) {
if (!upper(lc[i][a], b)) a = lc[i][a];
}
return lc[0][a];
}
struct fen {
int tree[N + N];
fen() {
memset(tree, 0, sizeof tree);
}
void upd(int pos, int val) {
while (pos < N + N) {
tree[pos] += val;
pos = pos | pos + 1;
}
}
int get(int r) {
int res = 0;
while (r >= 0) {
res += tree[r];
r = (r & r + 1) - 1;
}
return res;
}
int get(int l, int r) {
if (l > r) return 0;
return get(r) - get(l - 1);
}
};
fen tr, tr1;
int dp[N], dp1[N];
void dfs1(int v, int pr) {
for (int to : gr[v]) {
if (to == pr) continue;
dfs1(to, v);
dp1[v] += dp[to];
}
dp[v] = dp1[v];
for (int id : query[v]) {
int a, b;
tie(a, b) = make_tuple(get<0>(vec[id]), get<1>(vec[id]));
dp[v] = max(dp[v], dp1[v] + tr1.get(tin[v], tin[a]) + tr1.get(tin[v], tin[b]) - tr.get(tin[v], tin[a]) - tr.get(tin[v], tin[b]) + get<2>(vec[id]));
}
tr1.upd(tin[v], dp1[v]);
tr1.upd(tout[v], -dp1[v]);
tr.upd(tin[v], dp[v]);
tr.upd(tout[v], -dp[v]);
}
main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
gr[u].push_back(v);
gr[v].push_back(u);
}
dfs(1, 1);
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
if (tin[u] > tin[v]) swap(u, v);
vec.push_back({u, v, w});
query[lca(u, v)].push_back(i);
}
dfs1(1, 1);
printf("%d\n", dp[1]);
}
Compilation message
election_campaign.cpp: In member function 'void fen::upd(int, int)':
election_campaign.cpp:50:23: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
pos = pos | pos + 1;
~~~~^~~
election_campaign.cpp: In member function 'int fen::get(int)':
election_campaign.cpp:57:18: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
r = (r & r + 1) - 1;
~~^~~
election_campaign.cpp: At global scope:
election_campaign.cpp:88:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
election_campaign.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
election_campaign.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
election_campaign.cpp:100:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
6648 KB |
Output is correct |
2 |
Correct |
7 ms |
6648 KB |
Output is correct |
3 |
Correct |
8 ms |
6648 KB |
Output is correct |
4 |
Correct |
8 ms |
6776 KB |
Output is correct |
5 |
Correct |
134 ms |
19192 KB |
Output is correct |
6 |
Correct |
75 ms |
26944 KB |
Output is correct |
7 |
Correct |
137 ms |
24140 KB |
Output is correct |
8 |
Correct |
117 ms |
19192 KB |
Output is correct |
9 |
Correct |
136 ms |
22524 KB |
Output is correct |
10 |
Correct |
111 ms |
19064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
6648 KB |
Output is correct |
2 |
Correct |
8 ms |
6648 KB |
Output is correct |
3 |
Correct |
8 ms |
6904 KB |
Output is correct |
4 |
Correct |
144 ms |
29400 KB |
Output is correct |
5 |
Correct |
146 ms |
29296 KB |
Output is correct |
6 |
Correct |
146 ms |
29352 KB |
Output is correct |
7 |
Correct |
148 ms |
29484 KB |
Output is correct |
8 |
Correct |
146 ms |
29352 KB |
Output is correct |
9 |
Correct |
165 ms |
29404 KB |
Output is correct |
10 |
Correct |
147 ms |
29352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
6648 KB |
Output is correct |
2 |
Correct |
8 ms |
6648 KB |
Output is correct |
3 |
Correct |
8 ms |
6904 KB |
Output is correct |
4 |
Correct |
144 ms |
29400 KB |
Output is correct |
5 |
Correct |
146 ms |
29296 KB |
Output is correct |
6 |
Correct |
146 ms |
29352 KB |
Output is correct |
7 |
Correct |
148 ms |
29484 KB |
Output is correct |
8 |
Correct |
146 ms |
29352 KB |
Output is correct |
9 |
Correct |
165 ms |
29404 KB |
Output is correct |
10 |
Correct |
147 ms |
29352 KB |
Output is correct |
11 |
Correct |
19 ms |
7672 KB |
Output is correct |
12 |
Correct |
150 ms |
29444 KB |
Output is correct |
13 |
Correct |
148 ms |
29484 KB |
Output is correct |
14 |
Correct |
143 ms |
29620 KB |
Output is correct |
15 |
Correct |
197 ms |
29456 KB |
Output is correct |
16 |
Correct |
163 ms |
29552 KB |
Output is correct |
17 |
Correct |
152 ms |
29548 KB |
Output is correct |
18 |
Correct |
155 ms |
29564 KB |
Output is correct |
19 |
Correct |
149 ms |
29456 KB |
Output is correct |
20 |
Correct |
150 ms |
29612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
256 ms |
20952 KB |
Output is correct |
2 |
Correct |
144 ms |
29324 KB |
Output is correct |
3 |
Correct |
291 ms |
26140 KB |
Output is correct |
4 |
Correct |
222 ms |
21032 KB |
Output is correct |
5 |
Correct |
248 ms |
25776 KB |
Output is correct |
6 |
Correct |
232 ms |
21104 KB |
Output is correct |
7 |
Correct |
286 ms |
25388 KB |
Output is correct |
8 |
Correct |
270 ms |
21396 KB |
Output is correct |
9 |
Correct |
140 ms |
29208 KB |
Output is correct |
10 |
Correct |
281 ms |
24556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
6648 KB |
Output is correct |
2 |
Correct |
7 ms |
6648 KB |
Output is correct |
3 |
Correct |
8 ms |
6648 KB |
Output is correct |
4 |
Correct |
8 ms |
6776 KB |
Output is correct |
5 |
Correct |
134 ms |
19192 KB |
Output is correct |
6 |
Correct |
75 ms |
26944 KB |
Output is correct |
7 |
Correct |
137 ms |
24140 KB |
Output is correct |
8 |
Correct |
117 ms |
19192 KB |
Output is correct |
9 |
Correct |
136 ms |
22524 KB |
Output is correct |
10 |
Correct |
111 ms |
19064 KB |
Output is correct |
11 |
Correct |
9 ms |
6776 KB |
Output is correct |
12 |
Correct |
9 ms |
6904 KB |
Output is correct |
13 |
Correct |
9 ms |
6904 KB |
Output is correct |
14 |
Correct |
9 ms |
6808 KB |
Output is correct |
15 |
Correct |
9 ms |
6812 KB |
Output is correct |
16 |
Correct |
9 ms |
6904 KB |
Output is correct |
17 |
Correct |
9 ms |
6776 KB |
Output is correct |
18 |
Correct |
9 ms |
6904 KB |
Output is correct |
19 |
Correct |
9 ms |
6780 KB |
Output is correct |
20 |
Correct |
9 ms |
6904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
6648 KB |
Output is correct |
2 |
Correct |
7 ms |
6648 KB |
Output is correct |
3 |
Correct |
8 ms |
6648 KB |
Output is correct |
4 |
Correct |
8 ms |
6776 KB |
Output is correct |
5 |
Correct |
134 ms |
19192 KB |
Output is correct |
6 |
Correct |
75 ms |
26944 KB |
Output is correct |
7 |
Correct |
137 ms |
24140 KB |
Output is correct |
8 |
Correct |
117 ms |
19192 KB |
Output is correct |
9 |
Correct |
136 ms |
22524 KB |
Output is correct |
10 |
Correct |
111 ms |
19064 KB |
Output is correct |
11 |
Correct |
8 ms |
6648 KB |
Output is correct |
12 |
Correct |
8 ms |
6648 KB |
Output is correct |
13 |
Correct |
8 ms |
6904 KB |
Output is correct |
14 |
Correct |
144 ms |
29400 KB |
Output is correct |
15 |
Correct |
146 ms |
29296 KB |
Output is correct |
16 |
Correct |
146 ms |
29352 KB |
Output is correct |
17 |
Correct |
148 ms |
29484 KB |
Output is correct |
18 |
Correct |
146 ms |
29352 KB |
Output is correct |
19 |
Correct |
165 ms |
29404 KB |
Output is correct |
20 |
Correct |
147 ms |
29352 KB |
Output is correct |
21 |
Correct |
19 ms |
7672 KB |
Output is correct |
22 |
Correct |
150 ms |
29444 KB |
Output is correct |
23 |
Correct |
148 ms |
29484 KB |
Output is correct |
24 |
Correct |
143 ms |
29620 KB |
Output is correct |
25 |
Correct |
197 ms |
29456 KB |
Output is correct |
26 |
Correct |
163 ms |
29552 KB |
Output is correct |
27 |
Correct |
152 ms |
29548 KB |
Output is correct |
28 |
Correct |
155 ms |
29564 KB |
Output is correct |
29 |
Correct |
149 ms |
29456 KB |
Output is correct |
30 |
Correct |
150 ms |
29612 KB |
Output is correct |
31 |
Correct |
256 ms |
20952 KB |
Output is correct |
32 |
Correct |
144 ms |
29324 KB |
Output is correct |
33 |
Correct |
291 ms |
26140 KB |
Output is correct |
34 |
Correct |
222 ms |
21032 KB |
Output is correct |
35 |
Correct |
248 ms |
25776 KB |
Output is correct |
36 |
Correct |
232 ms |
21104 KB |
Output is correct |
37 |
Correct |
286 ms |
25388 KB |
Output is correct |
38 |
Correct |
270 ms |
21396 KB |
Output is correct |
39 |
Correct |
140 ms |
29208 KB |
Output is correct |
40 |
Correct |
281 ms |
24556 KB |
Output is correct |
41 |
Correct |
9 ms |
6776 KB |
Output is correct |
42 |
Correct |
9 ms |
6904 KB |
Output is correct |
43 |
Correct |
9 ms |
6904 KB |
Output is correct |
44 |
Correct |
9 ms |
6808 KB |
Output is correct |
45 |
Correct |
9 ms |
6812 KB |
Output is correct |
46 |
Correct |
9 ms |
6904 KB |
Output is correct |
47 |
Correct |
9 ms |
6776 KB |
Output is correct |
48 |
Correct |
9 ms |
6904 KB |
Output is correct |
49 |
Correct |
9 ms |
6780 KB |
Output is correct |
50 |
Correct |
9 ms |
6904 KB |
Output is correct |
51 |
Correct |
271 ms |
21436 KB |
Output is correct |
52 |
Correct |
148 ms |
31180 KB |
Output is correct |
53 |
Correct |
287 ms |
26632 KB |
Output is correct |
54 |
Correct |
197 ms |
23024 KB |
Output is correct |
55 |
Correct |
269 ms |
23036 KB |
Output is correct |
56 |
Correct |
152 ms |
31144 KB |
Output is correct |
57 |
Correct |
256 ms |
27304 KB |
Output is correct |
58 |
Correct |
255 ms |
23124 KB |
Output is correct |
59 |
Correct |
265 ms |
23336 KB |
Output is correct |
60 |
Correct |
148 ms |
31088 KB |
Output is correct |
61 |
Correct |
246 ms |
27408 KB |
Output is correct |
62 |
Correct |
222 ms |
23260 KB |
Output is correct |
63 |
Correct |
273 ms |
23080 KB |
Output is correct |
64 |
Correct |
146 ms |
31144 KB |
Output is correct |
65 |
Correct |
287 ms |
27316 KB |
Output is correct |
66 |
Correct |
192 ms |
23076 KB |
Output is correct |
67 |
Correct |
252 ms |
23068 KB |
Output is correct |
68 |
Correct |
147 ms |
31268 KB |
Output is correct |
69 |
Correct |
243 ms |
26280 KB |
Output is correct |
70 |
Correct |
222 ms |
23212 KB |
Output is correct |