#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pi pair<int, int>
#define pb push_back
struct sc {
int s1, s2, val, a, b;
};
constexpr int LIM = 1e5;
constexpr int base = (1 << 17);
vector<int>g[LIM + 10];
int pre[LIM + 10];
int post[LIM + 10];
int nxt[LIM + 10][18];
ll dp[LIM + 10][2];
vector<sc>zap[LIM + 10];
ll tri[2 * base][2];
int ojhld[LIM + 10];
int siz[LIM + 10];
bool czy(int a, int b) {
return pre[a] <= pre[b] && post[a] >= post[b];
}
pair<int, pi> lca(int a, int b) {
if(pre[a] <= pre[b]) {
swap(a, b);
}
for(int i = 17; i >= 0; i--) {
if(!czy(nxt[a][i], b)) {
a = nxt[a][i];
}
}
if(nxt[a][0] == b) {
return {nxt[a][0], {a, 0}};
}
for(int i = 17; i >= 0; i--) {
if(!czy(nxt[b][i], a)) {
b = nxt[b][i];
}
}
return {nxt[a][0], {a, b}};
}
void prepare(int v, int o) {
siz[v] = 1;
int mx = 0;
for(auto x : g[v]) {
if(x != o) {
prepare(x, v);
siz[v] += siz[x];
mx = max(mx, siz[x]);
}
}
for(int i = 0; i < g[v].size(); i++) {
if(g[v][i] != o && siz[g[v][i]] == mx) {
swap(g[v][i], g[v][0]);
}
}
}
int aktpre = 1, aktpost = 1;
void dfs(int v, int o) {
pre[v] = aktpre++;
nxt[v][0] = o;
for(int i = 1; i <= 17; i++) {
nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
}
for(int i = 0; i < g[v].size(); i++) {
if(g[v][i] != o) {
if(i) {
ojhld[g[v][i]] = g[v][i];
}
else {
ojhld[g[v][i]] = ojhld[v];
}
dfs(g[v][i], v);
}
}
post[v] = aktpost++;
}
void upd(int v, ll x, int k) {
v += base;
tri[v][k] = x;
v /= 2;
while(v > 0) {
tri[v][k] = tri[2 * v][k] + tri[2 * v + 1][k];
v /= 2;
}
}
ll que(int l, int r, int k) {
l += base;
r += base;
ll ans = 0;
while(l <= r) {
if(l & 1) {
ans += tri[l][k];
}
if(!(r & 1)) {
ans += tri[r][k];
}
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return ans;
}
ll hld(int a, int b, int k) {
//cout << "\nHLD " << a << ' ' << b << ' ' << k << '\n';
ll ans = 0;
while(pre[a] >= pre[b]) {
if(pre[ojhld[a]] <= pre[b]) {
//cout << a << ' ' << b << ' ' << que(pre[b], pre[a], k) << '\n';
ans += que(pre[b], pre[a], k);
break;
}
else {
//cout << a << ' ' << ojhld[a] << ' ' << que(pre[ojhld[a]], pre[a], k) << '\n';;
ans += que(pre[ojhld[a]], pre[a], k);
a = nxt[ojhld[a]][0];
}
}
//cout << "KONIEC\n";
return ans;
}
void cntdp(int v, int o) {
int sum = 0;
for(auto x : g[v]) {
if(x != o) {
cntdp(x, v);
sum += max(dp[x][0], dp[x][1]);
}
}
dp[v][0] = sum;
upd(pre[v], dp[v][0], 0);
for(auto x : zap[v]) {
if(x.b == v) {
//cout << x.a << ' ' << x.b << ' ' << v << ' ' << x.val << ' ' << hld(x.a, v, 0) << ' ' << hld(x.a, x.s1, 1) << '\n';
dp[v][1] = max(dp[v][1], hld(x.a, v, 0) - hld(x.a, x.s1, 1) + x.val);
}
else {
//cout << v << ' ' << x.a << ' ' << x.b << ' ' << x.val << ' ' << hld(x.a, v, 0) << ' ' << hld(x.a, x.s1, 1) << ' ' << hld(x.b, x.s2, 1) << '\n';
dp[v][1] = max(dp[v][1], hld(x.a, v, 0) - hld(x.a, x.s1, 1) + hld(x.b, x.s2, 0) - hld(x.b, x.s2, 1) + x.val);
}
}
//cout << v << ' ' << dp[v][0] << ' ' << dp[v][1] << '\n';
upd(pre[v], max(dp[v][0], dp[v][1]), 1);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
prepare(1, 1);
ojhld[1] = 1;
dfs(1, 1);
int t;
cin >> t;
for(int i = 1; i <= t; i++) {
int a, b, x;
cin >> a >> b >> x;
pair<int, pi> tmp = lca(a, b);
sc tmp2;
if(pre[a] <= pre[b]) {
swap(a, b);
}
tmp2.a = a;
tmp2.b = b;
tmp2.val = x;
tmp2.s1 = tmp.nd.st;
tmp2.s2 = tmp.nd.nd;
zap[tmp.st].pb(tmp2);
}
cntdp(1, 1);
cout << max(dp[1][0], dp[1][1]) << '\n';
}
Compilation message
election_campaign.cpp: In function 'void prepare(int, int)':
election_campaign.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i = 0; i < g[v].size(); i++) {
| ~~^~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < g[v].size(); i++) {
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5040 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
4 ms |
5204 KB |
Output is correct |
5 |
Correct |
117 ms |
22704 KB |
Output is correct |
6 |
Correct |
57 ms |
36644 KB |
Output is correct |
7 |
Correct |
100 ms |
31824 KB |
Output is correct |
8 |
Correct |
82 ms |
23048 KB |
Output is correct |
9 |
Correct |
113 ms |
29024 KB |
Output is correct |
10 |
Correct |
80 ms |
23088 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
4 ms |
5036 KB |
Output is correct |
3 |
Correct |
4 ms |
5332 KB |
Output is correct |
4 |
Correct |
144 ms |
40924 KB |
Output is correct |
5 |
Correct |
170 ms |
40936 KB |
Output is correct |
6 |
Correct |
160 ms |
40956 KB |
Output is correct |
7 |
Correct |
154 ms |
40984 KB |
Output is correct |
8 |
Correct |
160 ms |
40940 KB |
Output is correct |
9 |
Correct |
136 ms |
41012 KB |
Output is correct |
10 |
Correct |
143 ms |
40956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
4 ms |
5036 KB |
Output is correct |
3 |
Correct |
4 ms |
5332 KB |
Output is correct |
4 |
Correct |
144 ms |
40924 KB |
Output is correct |
5 |
Correct |
170 ms |
40936 KB |
Output is correct |
6 |
Correct |
160 ms |
40956 KB |
Output is correct |
7 |
Correct |
154 ms |
40984 KB |
Output is correct |
8 |
Correct |
160 ms |
40940 KB |
Output is correct |
9 |
Correct |
136 ms |
41012 KB |
Output is correct |
10 |
Correct |
143 ms |
40956 KB |
Output is correct |
11 |
Correct |
16 ms |
6480 KB |
Output is correct |
12 |
Correct |
153 ms |
41304 KB |
Output is correct |
13 |
Correct |
146 ms |
41300 KB |
Output is correct |
14 |
Correct |
130 ms |
41220 KB |
Output is correct |
15 |
Correct |
165 ms |
41292 KB |
Output is correct |
16 |
Correct |
129 ms |
41232 KB |
Output is correct |
17 |
Correct |
155 ms |
41304 KB |
Output is correct |
18 |
Correct |
151 ms |
41224 KB |
Output is correct |
19 |
Correct |
134 ms |
41252 KB |
Output is correct |
20 |
Correct |
145 ms |
41212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
229 ms |
26520 KB |
Output is correct |
2 |
Correct |
136 ms |
40996 KB |
Output is correct |
3 |
Correct |
253 ms |
35496 KB |
Output is correct |
4 |
Correct |
163 ms |
27100 KB |
Output is correct |
5 |
Correct |
228 ms |
34572 KB |
Output is correct |
6 |
Correct |
141 ms |
26884 KB |
Output is correct |
7 |
Correct |
272 ms |
34192 KB |
Output is correct |
8 |
Correct |
196 ms |
26820 KB |
Output is correct |
9 |
Correct |
147 ms |
41020 KB |
Output is correct |
10 |
Correct |
249 ms |
32464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5040 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
4 ms |
5204 KB |
Output is correct |
5 |
Correct |
117 ms |
22704 KB |
Output is correct |
6 |
Correct |
57 ms |
36644 KB |
Output is correct |
7 |
Correct |
100 ms |
31824 KB |
Output is correct |
8 |
Correct |
82 ms |
23048 KB |
Output is correct |
9 |
Correct |
113 ms |
29024 KB |
Output is correct |
10 |
Correct |
80 ms |
23088 KB |
Output is correct |
11 |
Correct |
4 ms |
5304 KB |
Output is correct |
12 |
Correct |
4 ms |
5460 KB |
Output is correct |
13 |
Correct |
4 ms |
5332 KB |
Output is correct |
14 |
Correct |
4 ms |
5332 KB |
Output is correct |
15 |
Correct |
4 ms |
5332 KB |
Output is correct |
16 |
Correct |
4 ms |
5352 KB |
Output is correct |
17 |
Correct |
4 ms |
5332 KB |
Output is correct |
18 |
Correct |
4 ms |
5304 KB |
Output is correct |
19 |
Correct |
4 ms |
5332 KB |
Output is correct |
20 |
Correct |
4 ms |
5432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5040 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
4 ms |
5204 KB |
Output is correct |
5 |
Correct |
117 ms |
22704 KB |
Output is correct |
6 |
Correct |
57 ms |
36644 KB |
Output is correct |
7 |
Correct |
100 ms |
31824 KB |
Output is correct |
8 |
Correct |
82 ms |
23048 KB |
Output is correct |
9 |
Correct |
113 ms |
29024 KB |
Output is correct |
10 |
Correct |
80 ms |
23088 KB |
Output is correct |
11 |
Correct |
3 ms |
5076 KB |
Output is correct |
12 |
Correct |
4 ms |
5036 KB |
Output is correct |
13 |
Correct |
4 ms |
5332 KB |
Output is correct |
14 |
Correct |
144 ms |
40924 KB |
Output is correct |
15 |
Correct |
170 ms |
40936 KB |
Output is correct |
16 |
Correct |
160 ms |
40956 KB |
Output is correct |
17 |
Correct |
154 ms |
40984 KB |
Output is correct |
18 |
Correct |
160 ms |
40940 KB |
Output is correct |
19 |
Correct |
136 ms |
41012 KB |
Output is correct |
20 |
Correct |
143 ms |
40956 KB |
Output is correct |
21 |
Correct |
16 ms |
6480 KB |
Output is correct |
22 |
Correct |
153 ms |
41304 KB |
Output is correct |
23 |
Correct |
146 ms |
41300 KB |
Output is correct |
24 |
Correct |
130 ms |
41220 KB |
Output is correct |
25 |
Correct |
165 ms |
41292 KB |
Output is correct |
26 |
Correct |
129 ms |
41232 KB |
Output is correct |
27 |
Correct |
155 ms |
41304 KB |
Output is correct |
28 |
Correct |
151 ms |
41224 KB |
Output is correct |
29 |
Correct |
134 ms |
41252 KB |
Output is correct |
30 |
Correct |
145 ms |
41212 KB |
Output is correct |
31 |
Correct |
229 ms |
26520 KB |
Output is correct |
32 |
Correct |
136 ms |
40996 KB |
Output is correct |
33 |
Correct |
253 ms |
35496 KB |
Output is correct |
34 |
Correct |
163 ms |
27100 KB |
Output is correct |
35 |
Correct |
228 ms |
34572 KB |
Output is correct |
36 |
Correct |
141 ms |
26884 KB |
Output is correct |
37 |
Correct |
272 ms |
34192 KB |
Output is correct |
38 |
Correct |
196 ms |
26820 KB |
Output is correct |
39 |
Correct |
147 ms |
41020 KB |
Output is correct |
40 |
Correct |
249 ms |
32464 KB |
Output is correct |
41 |
Correct |
4 ms |
5304 KB |
Output is correct |
42 |
Correct |
4 ms |
5460 KB |
Output is correct |
43 |
Correct |
4 ms |
5332 KB |
Output is correct |
44 |
Correct |
4 ms |
5332 KB |
Output is correct |
45 |
Correct |
4 ms |
5332 KB |
Output is correct |
46 |
Correct |
4 ms |
5352 KB |
Output is correct |
47 |
Correct |
4 ms |
5332 KB |
Output is correct |
48 |
Correct |
4 ms |
5304 KB |
Output is correct |
49 |
Correct |
4 ms |
5332 KB |
Output is correct |
50 |
Correct |
4 ms |
5432 KB |
Output is correct |
51 |
Correct |
214 ms |
27040 KB |
Output is correct |
52 |
Correct |
178 ms |
41180 KB |
Output is correct |
53 |
Correct |
244 ms |
32948 KB |
Output is correct |
54 |
Correct |
138 ms |
27332 KB |
Output is correct |
55 |
Correct |
219 ms |
26728 KB |
Output is correct |
56 |
Correct |
168 ms |
41272 KB |
Output is correct |
57 |
Correct |
211 ms |
34080 KB |
Output is correct |
58 |
Correct |
144 ms |
27232 KB |
Output is correct |
59 |
Correct |
221 ms |
27000 KB |
Output is correct |
60 |
Correct |
175 ms |
41252 KB |
Output is correct |
61 |
Correct |
229 ms |
34140 KB |
Output is correct |
62 |
Correct |
170 ms |
26896 KB |
Output is correct |
63 |
Correct |
209 ms |
26476 KB |
Output is correct |
64 |
Correct |
165 ms |
41288 KB |
Output is correct |
65 |
Correct |
284 ms |
34184 KB |
Output is correct |
66 |
Correct |
133 ms |
27036 KB |
Output is correct |
67 |
Correct |
249 ms |
26616 KB |
Output is correct |
68 |
Correct |
165 ms |
41332 KB |
Output is correct |
69 |
Correct |
225 ms |
31884 KB |
Output is correct |
70 |
Correct |
144 ms |
27080 KB |
Output is correct |