#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <chrono>
#include <random>
#include <bitset>
#include <utility>
int n, timer;
int tin[100005], tout[100005], up[20][100005];
std::vector <int> Adj[100005];
int m;
int A[100005], B[100005], C[100005];
int dp[100005];
std::vector <int> Query[100005];
int BIT[100005];
void Add(int id, int value)
{
for(id; id <= n; id += id & -id)
{
BIT[id] += value;
}
}
int Get(int id)
{
int ans = 0;
for(id; id > 0; id -= id & -id)
{
ans += BIT[id];
}
return ans;
}
void DFS(int node, int p)
{
timer++;
tin[node] = timer;
up[0][node] = p;
for(int i = 1; i <= 19; i++)
{
up[i][node] = up[i - 1][up[i - 1][node]];
}
for(auto x : Adj[node])
{
if(x == p)
{
continue;
}
DFS(x, node);
}
tout[node] = timer;
}
int Isparent(int u, int v)
{
return tin[u] <= tin[v] and tout[u] >= tout[v];
}
int LCA(int u, int v)
{
if(Isparent(u, v))
{
return u;
}
for(int i = 19; i >= 0; i--)
{
if(!Isparent(up[i][u], v))
{
u = up[i][u];
}
}
return up[0][u];
}
int Subtree(int u, int v)
{
assert(Isparent(u, v));
for(int i = 19; i >= 0; i--)
{
if(!Isparent(up[i][v], u))
{
v = up[i][v];
}
}
return v;
}
void Caldp(int node, int p)
{
int sumdp = 0;
for(auto x : Adj[node])
{
if(x == p)
{
continue;
}
Caldp(x, node);
sumdp += dp[x];
dp[node] = std::max(dp[node], dp[x]);
}
dp[node] = std::max(dp[node], sumdp);
for(auto x : Query[node])
{
if(A[x] == B[x])
{
dp[node] = std::max(dp[node], sumdp + C[x]);
}
else if(A[x] == node)
{
dp[node] = std::max(dp[node], sumdp - dp[Subtree(A[x], B[x])] + Get(tin[B[x]]) + C[x]);
}
else if(B[x] == node)
{
dp[node] = std::max(dp[node], sumdp - dp[Subtree(B[x], A[x])] + Get(tin[A[x]]) + C[x]);
}
else
{
dp[node] = std::max(dp[node], sumdp - dp[Subtree(node, A[x])] - dp[Subtree(node, B[x])] + Get(tin[A[x]]) + Get(tin[B[x]]) + C[x]);
}
}
for(auto x : Adj[node])
{
if(x == p)
{
continue;
}
Add(tin[x], sumdp - dp[x]);
Add(tout[x] + 1, dp[x] - sumdp);
}
Add(tin[node], sumdp);
Add(tin[node] + 1, -sumdp);
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n;
for(int i = 1; i < n; i++)
{
int u, v;
std::cin >> u >> v;
Adj[u].push_back(v);
Adj[v].push_back(u);
}
DFS(1, 1);
std::cin >> m;
for(int i = 1; i <= m; i++)
{
std::cin >> A[i] >> B[i] >> C[i];
Query[LCA(A[i], B[i])].push_back(i);
}
Caldp(1, 1);
std::cout << *std::max_element(dp + 1, dp + n + 1);
}
Compilation message
election_campaign.cpp: In function 'void Add(int, int)':
election_campaign.cpp:29:6: warning: statement has no effect [-Wunused-value]
29 | for(id; id <= n; id += id & -id)
| ^~
election_campaign.cpp: In function 'int Get(int)':
election_campaign.cpp:38:6: warning: statement has no effect [-Wunused-value]
38 | for(id; id > 0; id -= id & -id)
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5100 KB |
Output is correct |
4 |
Correct |
5 ms |
5356 KB |
Output is correct |
5 |
Correct |
125 ms |
18924 KB |
Output is correct |
6 |
Correct |
60 ms |
33004 KB |
Output is correct |
7 |
Correct |
135 ms |
28012 KB |
Output is correct |
8 |
Correct |
112 ms |
19436 KB |
Output is correct |
9 |
Correct |
129 ms |
25196 KB |
Output is correct |
10 |
Correct |
97 ms |
19308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5484 KB |
Output is correct |
4 |
Correct |
201 ms |
34028 KB |
Output is correct |
5 |
Correct |
199 ms |
34044 KB |
Output is correct |
6 |
Correct |
143 ms |
34028 KB |
Output is correct |
7 |
Correct |
208 ms |
34028 KB |
Output is correct |
8 |
Correct |
176 ms |
34028 KB |
Output is correct |
9 |
Correct |
143 ms |
34028 KB |
Output is correct |
10 |
Correct |
195 ms |
34156 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5484 KB |
Output is correct |
4 |
Correct |
201 ms |
34028 KB |
Output is correct |
5 |
Correct |
199 ms |
34044 KB |
Output is correct |
6 |
Correct |
143 ms |
34028 KB |
Output is correct |
7 |
Correct |
208 ms |
34028 KB |
Output is correct |
8 |
Correct |
176 ms |
34028 KB |
Output is correct |
9 |
Correct |
143 ms |
34028 KB |
Output is correct |
10 |
Correct |
195 ms |
34156 KB |
Output is correct |
11 |
Correct |
20 ms |
5996 KB |
Output is correct |
12 |
Correct |
213 ms |
34092 KB |
Output is correct |
13 |
Correct |
199 ms |
34028 KB |
Output is correct |
14 |
Correct |
157 ms |
34156 KB |
Output is correct |
15 |
Correct |
235 ms |
34028 KB |
Output is correct |
16 |
Correct |
146 ms |
34028 KB |
Output is correct |
17 |
Correct |
186 ms |
34028 KB |
Output is correct |
18 |
Correct |
192 ms |
34028 KB |
Output is correct |
19 |
Correct |
164 ms |
34176 KB |
Output is correct |
20 |
Correct |
230 ms |
34052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
318 ms |
19432 KB |
Output is correct |
2 |
Correct |
197 ms |
36588 KB |
Output is correct |
3 |
Correct |
457 ms |
31084 KB |
Output is correct |
4 |
Correct |
331 ms |
22376 KB |
Output is correct |
5 |
Correct |
465 ms |
30316 KB |
Output is correct |
6 |
Correct |
318 ms |
22376 KB |
Output is correct |
7 |
Correct |
451 ms |
29940 KB |
Output is correct |
8 |
Correct |
454 ms |
22508 KB |
Output is correct |
9 |
Correct |
166 ms |
36460 KB |
Output is correct |
10 |
Correct |
411 ms |
28136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5100 KB |
Output is correct |
4 |
Correct |
5 ms |
5356 KB |
Output is correct |
5 |
Correct |
125 ms |
18924 KB |
Output is correct |
6 |
Correct |
60 ms |
33004 KB |
Output is correct |
7 |
Correct |
135 ms |
28012 KB |
Output is correct |
8 |
Correct |
112 ms |
19436 KB |
Output is correct |
9 |
Correct |
129 ms |
25196 KB |
Output is correct |
10 |
Correct |
97 ms |
19308 KB |
Output is correct |
11 |
Correct |
5 ms |
5356 KB |
Output is correct |
12 |
Correct |
6 ms |
5484 KB |
Output is correct |
13 |
Correct |
6 ms |
5356 KB |
Output is correct |
14 |
Correct |
5 ms |
5356 KB |
Output is correct |
15 |
Correct |
5 ms |
5356 KB |
Output is correct |
16 |
Correct |
5 ms |
5356 KB |
Output is correct |
17 |
Correct |
5 ms |
5356 KB |
Output is correct |
18 |
Correct |
5 ms |
5356 KB |
Output is correct |
19 |
Correct |
5 ms |
5356 KB |
Output is correct |
20 |
Correct |
5 ms |
5484 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
4 ms |
5100 KB |
Output is correct |
3 |
Correct |
5 ms |
5100 KB |
Output is correct |
4 |
Correct |
5 ms |
5356 KB |
Output is correct |
5 |
Correct |
125 ms |
18924 KB |
Output is correct |
6 |
Correct |
60 ms |
33004 KB |
Output is correct |
7 |
Correct |
135 ms |
28012 KB |
Output is correct |
8 |
Correct |
112 ms |
19436 KB |
Output is correct |
9 |
Correct |
129 ms |
25196 KB |
Output is correct |
10 |
Correct |
97 ms |
19308 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
13 |
Correct |
5 ms |
5484 KB |
Output is correct |
14 |
Correct |
201 ms |
34028 KB |
Output is correct |
15 |
Correct |
199 ms |
34044 KB |
Output is correct |
16 |
Correct |
143 ms |
34028 KB |
Output is correct |
17 |
Correct |
208 ms |
34028 KB |
Output is correct |
18 |
Correct |
176 ms |
34028 KB |
Output is correct |
19 |
Correct |
143 ms |
34028 KB |
Output is correct |
20 |
Correct |
195 ms |
34156 KB |
Output is correct |
21 |
Correct |
20 ms |
5996 KB |
Output is correct |
22 |
Correct |
213 ms |
34092 KB |
Output is correct |
23 |
Correct |
199 ms |
34028 KB |
Output is correct |
24 |
Correct |
157 ms |
34156 KB |
Output is correct |
25 |
Correct |
235 ms |
34028 KB |
Output is correct |
26 |
Correct |
146 ms |
34028 KB |
Output is correct |
27 |
Correct |
186 ms |
34028 KB |
Output is correct |
28 |
Correct |
192 ms |
34028 KB |
Output is correct |
29 |
Correct |
164 ms |
34176 KB |
Output is correct |
30 |
Correct |
230 ms |
34052 KB |
Output is correct |
31 |
Correct |
318 ms |
19432 KB |
Output is correct |
32 |
Correct |
197 ms |
36588 KB |
Output is correct |
33 |
Correct |
457 ms |
31084 KB |
Output is correct |
34 |
Correct |
331 ms |
22376 KB |
Output is correct |
35 |
Correct |
465 ms |
30316 KB |
Output is correct |
36 |
Correct |
318 ms |
22376 KB |
Output is correct |
37 |
Correct |
451 ms |
29940 KB |
Output is correct |
38 |
Correct |
454 ms |
22508 KB |
Output is correct |
39 |
Correct |
166 ms |
36460 KB |
Output is correct |
40 |
Correct |
411 ms |
28136 KB |
Output is correct |
41 |
Correct |
5 ms |
5356 KB |
Output is correct |
42 |
Correct |
6 ms |
5484 KB |
Output is correct |
43 |
Correct |
6 ms |
5356 KB |
Output is correct |
44 |
Correct |
5 ms |
5356 KB |
Output is correct |
45 |
Correct |
5 ms |
5356 KB |
Output is correct |
46 |
Correct |
5 ms |
5356 KB |
Output is correct |
47 |
Correct |
5 ms |
5356 KB |
Output is correct |
48 |
Correct |
5 ms |
5356 KB |
Output is correct |
49 |
Correct |
5 ms |
5356 KB |
Output is correct |
50 |
Correct |
5 ms |
5484 KB |
Output is correct |
51 |
Correct |
486 ms |
22688 KB |
Output is correct |
52 |
Correct |
191 ms |
36736 KB |
Output is correct |
53 |
Correct |
505 ms |
28776 KB |
Output is correct |
54 |
Correct |
397 ms |
22588 KB |
Output is correct |
55 |
Correct |
367 ms |
22120 KB |
Output is correct |
56 |
Correct |
191 ms |
36716 KB |
Output is correct |
57 |
Correct |
444 ms |
29676 KB |
Output is correct |
58 |
Correct |
279 ms |
22636 KB |
Output is correct |
59 |
Correct |
531 ms |
22636 KB |
Output is correct |
60 |
Correct |
182 ms |
36716 KB |
Output is correct |
61 |
Correct |
450 ms |
29804 KB |
Output is correct |
62 |
Correct |
274 ms |
22444 KB |
Output is correct |
63 |
Correct |
321 ms |
22404 KB |
Output is correct |
64 |
Correct |
223 ms |
36588 KB |
Output is correct |
65 |
Correct |
459 ms |
29708 KB |
Output is correct |
66 |
Correct |
447 ms |
22704 KB |
Output is correct |
67 |
Correct |
341 ms |
22256 KB |
Output is correct |
68 |
Correct |
205 ms |
36588 KB |
Output is correct |
69 |
Correct |
458 ms |
27776 KB |
Output is correct |
70 |
Correct |
281 ms |
22540 KB |
Output is correct |