#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int MXN = 100005;
int n, m, a[MXN], b[MXN], c[MXN];
vector<int> lenid[MXN];
int lca[MXN], dfn[MXN];
ll dp[MXN];
struct BIT {
int n;
ll val[MXN];
void init(int _n) {
n = _n;
fill(val + 1, val + n + 1, 0);
}
void modify(int id, int v) {
for (; id <= n; id += (id & -id)) val[id] += v;
}
ll query(int id) {
ll ans = 0;
for (; id > 0; id -= (id & -id)) ans += val[id];
return ans;
}
ll query(int l, int r) {
return query(r) - query(l - 1);
}
} B;
namespace TREE {
int p[MXN], d[MXN], sz[MXN], son[MXN], top[MXN], C = 1;
vector<int> edge[MXN];
void ADD_EDGE(int x, int y) {
edge[x].push_back(y);
edge[y].push_back(x);
}
void DFS(int id, int par, int dep) {
p[id] = par;
d[id] = dep;
sz[id] = 1;
son[id] = -1;
for (auto &i : edge[id]) {
if (i == par) continue;
DFS(i, id, dep + 1);
sz[id] += sz[i];
if (son[id] == -1 || sz[son[id]] < sz[i]) son[id] = i;
}
}
void HLD(int id, int par, int _t) {
top[id] = _t;
dfn[id] = C++;
if (son[id] != -1) HLD(son[id], id, _t);
for (auto &i : edge[id]) {
if (i == par) continue;
if (i == son[id]) continue;
HLD(i, id, i);
}
}
void BUILD() {
DFS(1, 0, 0);
HLD(1, 0, 1);
}
int LCA(int x, int y) {
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
x = p[top[x]];
}
return (d[x] > d[y] ? y : x);
}
}
ll JUMP(int rt, int x) {
using namespace TREE;
ll ans = 0;
while (top[x] != top[rt]) {
ans += B.query(dfn[top[x]], dfn[x]);
x = p[top[x]];
}
return ans + B.query(dfn[rt] + 1, dfn[x]);
}
void DP(int id, int par) {
ll sum = 0;
for (auto &i : TREE::edge[id]) {
if (i == par) continue;
DP(i, id);
sum += dp[i];
}
dp[id] = sum;
for (auto &e : lenid[id]) {
debug(id, e, a[e], b[e]);
int l = JUMP(id, a[e]), r = JUMP(id, b[e]);
ll now = sum + c[e] - l - r;
debug(l, r, now);
dp[id] = max(dp[id], now);
}
B.modify(dfn[id], dp[id] - sum);
debug(id, dp[id], dp[id] - sum);
}
void miku() {
int x, y;
cin >> n;
FOR(i, 1, n) {
cin >> x >> y;
TREE::ADD_EDGE(x, y);
}
TREE::BUILD();
cin >> m;
FOR(i, 0, m) {
cin >> a[i] >> b[i] >> c[i];
lca[i] = TREE::LCA(a[i], b[i]);
lenid[lca[i]].push_back(i);
}
B.init(n);
DP(1, 0);
cout << dp[1] << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
Compilation message
election_campaign.cpp: In function 'void DP(int, int)':
election_campaign.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
election_campaign.cpp:111:3: note: in expansion of macro 'debug'
111 | debug(id, e, a[e], b[e]);
| ^~~~~
election_campaign.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
election_campaign.cpp:114:3: note: in expansion of macro 'debug'
114 | debug(l, r, now);
| ^~~~~
election_campaign.cpp:11:20: warning: statement has no effect [-Wunused-value]
11 | #define debug(...) 39
| ^~
election_campaign.cpp:118:2: note: in expansion of macro 'debug'
118 | debug(id, dp[id], dp[id] - sum);
| ^~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9456 KB |
Output is correct |
2 |
Correct |
2 ms |
9308 KB |
Output is correct |
3 |
Correct |
2 ms |
9308 KB |
Output is correct |
4 |
Correct |
2 ms |
9460 KB |
Output is correct |
5 |
Correct |
44 ms |
13908 KB |
Output is correct |
6 |
Correct |
41 ms |
24656 KB |
Output is correct |
7 |
Correct |
39 ms |
20820 KB |
Output is correct |
8 |
Correct |
25 ms |
14172 KB |
Output is correct |
9 |
Correct |
38 ms |
18480 KB |
Output is correct |
10 |
Correct |
28 ms |
14172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
2 ms |
9308 KB |
Output is correct |
3 |
Correct |
2 ms |
9564 KB |
Output is correct |
4 |
Correct |
68 ms |
28172 KB |
Output is correct |
5 |
Correct |
69 ms |
28120 KB |
Output is correct |
6 |
Correct |
60 ms |
28104 KB |
Output is correct |
7 |
Correct |
63 ms |
28056 KB |
Output is correct |
8 |
Correct |
70 ms |
28220 KB |
Output is correct |
9 |
Correct |
59 ms |
28272 KB |
Output is correct |
10 |
Correct |
66 ms |
28116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9308 KB |
Output is correct |
2 |
Correct |
2 ms |
9308 KB |
Output is correct |
3 |
Correct |
2 ms |
9564 KB |
Output is correct |
4 |
Correct |
68 ms |
28172 KB |
Output is correct |
5 |
Correct |
69 ms |
28120 KB |
Output is correct |
6 |
Correct |
60 ms |
28104 KB |
Output is correct |
7 |
Correct |
63 ms |
28056 KB |
Output is correct |
8 |
Correct |
70 ms |
28220 KB |
Output is correct |
9 |
Correct |
59 ms |
28272 KB |
Output is correct |
10 |
Correct |
66 ms |
28116 KB |
Output is correct |
11 |
Correct |
7 ms |
10332 KB |
Output is correct |
12 |
Correct |
77 ms |
28280 KB |
Output is correct |
13 |
Correct |
79 ms |
28580 KB |
Output is correct |
14 |
Correct |
65 ms |
28500 KB |
Output is correct |
15 |
Correct |
66 ms |
28424 KB |
Output is correct |
16 |
Correct |
74 ms |
28500 KB |
Output is correct |
17 |
Correct |
80 ms |
28520 KB |
Output is correct |
18 |
Correct |
69 ms |
28452 KB |
Output is correct |
19 |
Correct |
70 ms |
28496 KB |
Output is correct |
20 |
Correct |
72 ms |
28296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
100 ms |
16716 KB |
Output is correct |
2 |
Correct |
73 ms |
28300 KB |
Output is correct |
3 |
Correct |
84 ms |
23892 KB |
Output is correct |
4 |
Correct |
63 ms |
17016 KB |
Output is correct |
5 |
Correct |
78 ms |
23228 KB |
Output is correct |
6 |
Correct |
62 ms |
17328 KB |
Output is correct |
7 |
Correct |
91 ms |
23100 KB |
Output is correct |
8 |
Correct |
87 ms |
17328 KB |
Output is correct |
9 |
Correct |
66 ms |
28088 KB |
Output is correct |
10 |
Correct |
76 ms |
21716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9456 KB |
Output is correct |
2 |
Correct |
2 ms |
9308 KB |
Output is correct |
3 |
Correct |
2 ms |
9308 KB |
Output is correct |
4 |
Correct |
2 ms |
9460 KB |
Output is correct |
5 |
Correct |
44 ms |
13908 KB |
Output is correct |
6 |
Correct |
41 ms |
24656 KB |
Output is correct |
7 |
Correct |
39 ms |
20820 KB |
Output is correct |
8 |
Correct |
25 ms |
14172 KB |
Output is correct |
9 |
Correct |
38 ms |
18480 KB |
Output is correct |
10 |
Correct |
28 ms |
14172 KB |
Output is correct |
11 |
Correct |
2 ms |
9304 KB |
Output is correct |
12 |
Correct |
3 ms |
9564 KB |
Output is correct |
13 |
Correct |
3 ms |
9560 KB |
Output is correct |
14 |
Correct |
2 ms |
9308 KB |
Output is correct |
15 |
Correct |
3 ms |
9424 KB |
Output is correct |
16 |
Correct |
3 ms |
9568 KB |
Output is correct |
17 |
Correct |
2 ms |
9504 KB |
Output is correct |
18 |
Correct |
3 ms |
9564 KB |
Output is correct |
19 |
Correct |
4 ms |
9304 KB |
Output is correct |
20 |
Correct |
3 ms |
9564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
9456 KB |
Output is correct |
2 |
Correct |
2 ms |
9308 KB |
Output is correct |
3 |
Correct |
2 ms |
9308 KB |
Output is correct |
4 |
Correct |
2 ms |
9460 KB |
Output is correct |
5 |
Correct |
44 ms |
13908 KB |
Output is correct |
6 |
Correct |
41 ms |
24656 KB |
Output is correct |
7 |
Correct |
39 ms |
20820 KB |
Output is correct |
8 |
Correct |
25 ms |
14172 KB |
Output is correct |
9 |
Correct |
38 ms |
18480 KB |
Output is correct |
10 |
Correct |
28 ms |
14172 KB |
Output is correct |
11 |
Correct |
2 ms |
9308 KB |
Output is correct |
12 |
Correct |
2 ms |
9308 KB |
Output is correct |
13 |
Correct |
2 ms |
9564 KB |
Output is correct |
14 |
Correct |
68 ms |
28172 KB |
Output is correct |
15 |
Correct |
69 ms |
28120 KB |
Output is correct |
16 |
Correct |
60 ms |
28104 KB |
Output is correct |
17 |
Correct |
63 ms |
28056 KB |
Output is correct |
18 |
Correct |
70 ms |
28220 KB |
Output is correct |
19 |
Correct |
59 ms |
28272 KB |
Output is correct |
20 |
Correct |
66 ms |
28116 KB |
Output is correct |
21 |
Correct |
7 ms |
10332 KB |
Output is correct |
22 |
Correct |
77 ms |
28280 KB |
Output is correct |
23 |
Correct |
79 ms |
28580 KB |
Output is correct |
24 |
Correct |
65 ms |
28500 KB |
Output is correct |
25 |
Correct |
66 ms |
28424 KB |
Output is correct |
26 |
Correct |
74 ms |
28500 KB |
Output is correct |
27 |
Correct |
80 ms |
28520 KB |
Output is correct |
28 |
Correct |
69 ms |
28452 KB |
Output is correct |
29 |
Correct |
70 ms |
28496 KB |
Output is correct |
30 |
Correct |
72 ms |
28296 KB |
Output is correct |
31 |
Correct |
100 ms |
16716 KB |
Output is correct |
32 |
Correct |
73 ms |
28300 KB |
Output is correct |
33 |
Correct |
84 ms |
23892 KB |
Output is correct |
34 |
Correct |
63 ms |
17016 KB |
Output is correct |
35 |
Correct |
78 ms |
23228 KB |
Output is correct |
36 |
Correct |
62 ms |
17328 KB |
Output is correct |
37 |
Correct |
91 ms |
23100 KB |
Output is correct |
38 |
Correct |
87 ms |
17328 KB |
Output is correct |
39 |
Correct |
66 ms |
28088 KB |
Output is correct |
40 |
Correct |
76 ms |
21716 KB |
Output is correct |
41 |
Correct |
2 ms |
9304 KB |
Output is correct |
42 |
Correct |
3 ms |
9564 KB |
Output is correct |
43 |
Correct |
3 ms |
9560 KB |
Output is correct |
44 |
Correct |
2 ms |
9308 KB |
Output is correct |
45 |
Correct |
3 ms |
9424 KB |
Output is correct |
46 |
Correct |
3 ms |
9568 KB |
Output is correct |
47 |
Correct |
2 ms |
9504 KB |
Output is correct |
48 |
Correct |
3 ms |
9564 KB |
Output is correct |
49 |
Correct |
4 ms |
9304 KB |
Output is correct |
50 |
Correct |
3 ms |
9564 KB |
Output is correct |
51 |
Correct |
83 ms |
17600 KB |
Output is correct |
52 |
Correct |
63 ms |
28496 KB |
Output is correct |
53 |
Correct |
78 ms |
22172 KB |
Output is correct |
54 |
Correct |
61 ms |
17288 KB |
Output is correct |
55 |
Correct |
98 ms |
17172 KB |
Output is correct |
56 |
Correct |
66 ms |
28500 KB |
Output is correct |
57 |
Correct |
95 ms |
22952 KB |
Output is correct |
58 |
Correct |
62 ms |
17488 KB |
Output is correct |
59 |
Correct |
91 ms |
17568 KB |
Output is correct |
60 |
Correct |
64 ms |
28500 KB |
Output is correct |
61 |
Correct |
81 ms |
23188 KB |
Output is correct |
62 |
Correct |
64 ms |
17496 KB |
Output is correct |
63 |
Correct |
110 ms |
17228 KB |
Output is correct |
64 |
Correct |
66 ms |
28264 KB |
Output is correct |
65 |
Correct |
76 ms |
23104 KB |
Output is correct |
66 |
Correct |
54 ms |
17580 KB |
Output is correct |
67 |
Correct |
109 ms |
17292 KB |
Output is correct |
68 |
Correct |
64 ms |
28340 KB |
Output is correct |
69 |
Correct |
86 ms |
21328 KB |
Output is correct |
70 |
Correct |
73 ms |
17440 KB |
Output is correct |