// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 2e5 + 5;
const int lg = 18;
const int mod = 1e9 + 7;
const long long oo = 1e18;
const int lim = 1e6;
ll tin[N], tout[N], dp[N][19], f[N], dep[N];
ll timer = 0;
ll bit[N];
vector<ll> node[N];
struct viet{
ll u, v, c;
};
vector<viet> Q[N];
void upd(ll u, ll v){
ll res = 0;
for (int i = u; i <= timer; i += i & -i){
bit[i] += v;
}
}
ll get(ll u){
ll res = 0;
for (int i = u; i > 0; i -= i & -i) res += bit[i];
return res;
}
void dfs2(ll u, ll p){
for (auto j : node[u]){
if (j == p) continue;
dfs2(j, u);
upd(tin[u], f[j]);
upd(tout[u], -f[j]);
}
for (auto j : Q[u]){
f[u] = max(f[u], get(tin[j.u]) + get(tin[j.v]) - get(tin[u]) - get(tin[p]) + j.c);
}
f[u] = max(f[u], get(tin[u]) - get(tin[p]));
upd(tin[u], -f[u]);
upd(tout[u], f[u]);
}
void dfs(ll u, ll p){
timer++;
tin[u] = timer;
for (int i = 1; i <= lg; i++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
for (auto j : node[u]){
if (j == p) continue;
dp[j][0] = u;
dep[j] = dep[u] + 1;
dfs(j, u);
}
timer++;
tout[u] = timer;
}
ll LCA(ll u, ll v){
if (dep[u] > dep[v]) swap(u, v);
ll dis = dep[v] - dep[u];
for (int i = lg; i >= 0; i--){
if (dis & (1 << i)){
v = dp[v][i];
}
}
if (u == v) return u;
for (int i = lg; i >= 0; i--){
if (dp[u][i] != dp[v][i]){
u = dp[u][i];
v = dp[v][i];
}
}
return dp[u][0];
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("A.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n;
cin >> n;
for (int i = 1; i < n; i++){
ll u, v;
cin >> u >> v;
node[u].push_back(v);
node[v].push_back(u);
}
dfs(1, 1);
ll m;
cin >> m;
for (int i = 1; i <= m; i++){
ll u, v, c;
cin >> u >> v >> c;
ll lca = LCA(u, v);
Q[lca].push_back({u, v, c});
}
dfs2(1, 0);
cout << f[1];
}
/*
*/
Compilation message
election_campaign.cpp: In function 'void upd(long long int, long long int)':
election_campaign.cpp:20:8: warning: unused variable 'res' [-Wunused-variable]
20 | ll res = 0;
| ^~~
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
78 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
79 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
7 ms |
9708 KB |
Output is correct |
4 |
Correct |
8 ms |
9964 KB |
Output is correct |
5 |
Correct |
155 ms |
34412 KB |
Output is correct |
6 |
Correct |
284 ms |
42988 KB |
Output is correct |
7 |
Correct |
165 ms |
40300 KB |
Output is correct |
8 |
Correct |
117 ms |
34540 KB |
Output is correct |
9 |
Correct |
165 ms |
38380 KB |
Output is correct |
10 |
Correct |
117 ms |
34488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9836 KB |
Output is correct |
3 |
Correct |
8 ms |
10092 KB |
Output is correct |
4 |
Correct |
192 ms |
47852 KB |
Output is correct |
5 |
Correct |
197 ms |
47852 KB |
Output is correct |
6 |
Correct |
154 ms |
47980 KB |
Output is correct |
7 |
Correct |
190 ms |
47852 KB |
Output is correct |
8 |
Correct |
187 ms |
47852 KB |
Output is correct |
9 |
Correct |
158 ms |
47980 KB |
Output is correct |
10 |
Correct |
184 ms |
47852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9836 KB |
Output is correct |
3 |
Correct |
8 ms |
10092 KB |
Output is correct |
4 |
Correct |
192 ms |
47852 KB |
Output is correct |
5 |
Correct |
197 ms |
47852 KB |
Output is correct |
6 |
Correct |
154 ms |
47980 KB |
Output is correct |
7 |
Correct |
190 ms |
47852 KB |
Output is correct |
8 |
Correct |
187 ms |
47852 KB |
Output is correct |
9 |
Correct |
158 ms |
47980 KB |
Output is correct |
10 |
Correct |
184 ms |
47852 KB |
Output is correct |
11 |
Correct |
17 ms |
11368 KB |
Output is correct |
12 |
Correct |
191 ms |
48236 KB |
Output is correct |
13 |
Correct |
198 ms |
48108 KB |
Output is correct |
14 |
Correct |
183 ms |
48236 KB |
Output is correct |
15 |
Correct |
193 ms |
48108 KB |
Output is correct |
16 |
Correct |
167 ms |
48236 KB |
Output is correct |
17 |
Correct |
194 ms |
48108 KB |
Output is correct |
18 |
Correct |
194 ms |
48236 KB |
Output is correct |
19 |
Correct |
168 ms |
48256 KB |
Output is correct |
20 |
Correct |
205 ms |
48236 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
232 ms |
38780 KB |
Output is correct |
2 |
Correct |
177 ms |
47852 KB |
Output is correct |
3 |
Correct |
317 ms |
44584 KB |
Output is correct |
4 |
Correct |
181 ms |
39240 KB |
Output is correct |
5 |
Correct |
268 ms |
43944 KB |
Output is correct |
6 |
Correct |
172 ms |
38872 KB |
Output is correct |
7 |
Correct |
322 ms |
43692 KB |
Output is correct |
8 |
Correct |
251 ms |
38764 KB |
Output is correct |
9 |
Correct |
164 ms |
48108 KB |
Output is correct |
10 |
Correct |
323 ms |
42272 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
7 ms |
9708 KB |
Output is correct |
4 |
Correct |
8 ms |
9964 KB |
Output is correct |
5 |
Correct |
155 ms |
34412 KB |
Output is correct |
6 |
Correct |
284 ms |
42988 KB |
Output is correct |
7 |
Correct |
165 ms |
40300 KB |
Output is correct |
8 |
Correct |
117 ms |
34540 KB |
Output is correct |
9 |
Correct |
165 ms |
38380 KB |
Output is correct |
10 |
Correct |
117 ms |
34488 KB |
Output is correct |
11 |
Correct |
9 ms |
10092 KB |
Output is correct |
12 |
Correct |
8 ms |
10092 KB |
Output is correct |
13 |
Correct |
8 ms |
10092 KB |
Output is correct |
14 |
Correct |
8 ms |
10092 KB |
Output is correct |
15 |
Correct |
8 ms |
10092 KB |
Output is correct |
16 |
Correct |
8 ms |
10092 KB |
Output is correct |
17 |
Correct |
8 ms |
10092 KB |
Output is correct |
18 |
Correct |
9 ms |
10092 KB |
Output is correct |
19 |
Correct |
8 ms |
10092 KB |
Output is correct |
20 |
Correct |
9 ms |
10104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
7 ms |
9708 KB |
Output is correct |
4 |
Correct |
8 ms |
9964 KB |
Output is correct |
5 |
Correct |
155 ms |
34412 KB |
Output is correct |
6 |
Correct |
284 ms |
42988 KB |
Output is correct |
7 |
Correct |
165 ms |
40300 KB |
Output is correct |
8 |
Correct |
117 ms |
34540 KB |
Output is correct |
9 |
Correct |
165 ms |
38380 KB |
Output is correct |
10 |
Correct |
117 ms |
34488 KB |
Output is correct |
11 |
Correct |
8 ms |
9708 KB |
Output is correct |
12 |
Correct |
7 ms |
9836 KB |
Output is correct |
13 |
Correct |
8 ms |
10092 KB |
Output is correct |
14 |
Correct |
192 ms |
47852 KB |
Output is correct |
15 |
Correct |
197 ms |
47852 KB |
Output is correct |
16 |
Correct |
154 ms |
47980 KB |
Output is correct |
17 |
Correct |
190 ms |
47852 KB |
Output is correct |
18 |
Correct |
187 ms |
47852 KB |
Output is correct |
19 |
Correct |
158 ms |
47980 KB |
Output is correct |
20 |
Correct |
184 ms |
47852 KB |
Output is correct |
21 |
Correct |
17 ms |
11368 KB |
Output is correct |
22 |
Correct |
191 ms |
48236 KB |
Output is correct |
23 |
Correct |
198 ms |
48108 KB |
Output is correct |
24 |
Correct |
183 ms |
48236 KB |
Output is correct |
25 |
Correct |
193 ms |
48108 KB |
Output is correct |
26 |
Correct |
167 ms |
48236 KB |
Output is correct |
27 |
Correct |
194 ms |
48108 KB |
Output is correct |
28 |
Correct |
194 ms |
48236 KB |
Output is correct |
29 |
Correct |
168 ms |
48256 KB |
Output is correct |
30 |
Correct |
205 ms |
48236 KB |
Output is correct |
31 |
Correct |
232 ms |
38780 KB |
Output is correct |
32 |
Correct |
177 ms |
47852 KB |
Output is correct |
33 |
Correct |
317 ms |
44584 KB |
Output is correct |
34 |
Correct |
181 ms |
39240 KB |
Output is correct |
35 |
Correct |
268 ms |
43944 KB |
Output is correct |
36 |
Correct |
172 ms |
38872 KB |
Output is correct |
37 |
Correct |
322 ms |
43692 KB |
Output is correct |
38 |
Correct |
251 ms |
38764 KB |
Output is correct |
39 |
Correct |
164 ms |
48108 KB |
Output is correct |
40 |
Correct |
323 ms |
42272 KB |
Output is correct |
41 |
Correct |
9 ms |
10092 KB |
Output is correct |
42 |
Correct |
8 ms |
10092 KB |
Output is correct |
43 |
Correct |
8 ms |
10092 KB |
Output is correct |
44 |
Correct |
8 ms |
10092 KB |
Output is correct |
45 |
Correct |
8 ms |
10092 KB |
Output is correct |
46 |
Correct |
8 ms |
10092 KB |
Output is correct |
47 |
Correct |
8 ms |
10092 KB |
Output is correct |
48 |
Correct |
9 ms |
10092 KB |
Output is correct |
49 |
Correct |
8 ms |
10092 KB |
Output is correct |
50 |
Correct |
9 ms |
10104 KB |
Output is correct |
51 |
Correct |
242 ms |
38996 KB |
Output is correct |
52 |
Correct |
187 ms |
48108 KB |
Output is correct |
53 |
Correct |
340 ms |
42688 KB |
Output is correct |
54 |
Correct |
168 ms |
39136 KB |
Output is correct |
55 |
Correct |
226 ms |
38816 KB |
Output is correct |
56 |
Correct |
201 ms |
48108 KB |
Output is correct |
57 |
Correct |
268 ms |
43560 KB |
Output is correct |
58 |
Correct |
177 ms |
39080 KB |
Output is correct |
59 |
Correct |
234 ms |
39012 KB |
Output is correct |
60 |
Correct |
198 ms |
48108 KB |
Output is correct |
61 |
Correct |
281 ms |
43608 KB |
Output is correct |
62 |
Correct |
173 ms |
38880 KB |
Output is correct |
63 |
Correct |
235 ms |
38800 KB |
Output is correct |
64 |
Correct |
188 ms |
48236 KB |
Output is correct |
65 |
Correct |
339 ms |
43492 KB |
Output is correct |
66 |
Correct |
179 ms |
39068 KB |
Output is correct |
67 |
Correct |
227 ms |
38872 KB |
Output is correct |
68 |
Correct |
198 ms |
48220 KB |
Output is correct |
69 |
Correct |
272 ms |
42152 KB |
Output is correct |
70 |
Correct |
186 ms |
39060 KB |
Output is correct |