#include <bits/stdc++.h>
#define Y8o "Election Campaign"
#define maxn 100005
#define ll long long
#define pii pair<int, int>
#define gb(i, j) ((i >> j) & 1)
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r) (rng);
}
void iof() {
if(fopen(Y8o".inp", "r"))
{
freopen(Y8o".inp", "r", stdin);
// freopen(Y8o".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(NULL), cout.tie(NULL);
}
void ctime() {
cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}
int n, Q, cnt;
int h[maxn], cha[maxn][20];
int in[maxn], out[maxn];
vector<int> o[maxn];
struct dl { int u, v, w; }; vector<dl> qr[maxn];
void dfs(int u, int par = -1)
{
in[u] = ++ cnt;
for(int v : o[u])
{
if(v == par) continue;
h[v] = h[u] + 1, cha[v][0] = u;
for(int j = 1; j <= 17; j ++) cha[v][j] = cha[cha[v][j - 1]][j - 1];
dfs(v, u);
}
out[u] = cnt;
}
int lca(int u, int v)
{
if( h[u] < h[v] ) swap(u, v);
for(int i = 17; i >= 0; --i) if(h[u] - (1 << i) >= h[v]) u = cha[u][i];
for(int i = 17; i >= 0; --i) if(cha[u][i] != cha[v][i]) u = cha[u][i], v = cha[v][i];
return u == v ? u : cha[u][0];
}
struct BIT {
ll bit[maxn];
void update(int l, int r, ll val) {
for(; l < maxn; l += (l & -l)) bit[l] += val;
for(++r; r < maxn; r += (r & -r)) bit[r] -= val;
}
ll get(int x, ll ans = 0) {
for(; x; x -= (x & -x)) ans += bit[x];
return ans;
}
} B[2]; /// dp[u][0] || dp[u][0/1]
ll dp[maxn][2];
void dfs2(int u, int par = -1)
{
for(int v : o[u]) if(v != par)
{
dfs2(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
}
B[0].update(in[u], out[u], dp[u][0]);
for(dl x : qr[u])
{
int u1 = x.u, v1 = x.v, w = x.w;
if(h[u1] > h[v1]) swap(u1, v1);
ll best = 0;
ll val1[] = { B[0].get(in[u1]) - B[0].get(in[u]), B[1].get(in[u1]) - B[1].get(in[u]) };
ll val2[] = { B[0].get(in[v1]) - B[0].get(in[u]), B[1].get(in[v1]) - B[1].get(in[u]) };
if(u1 == u)
{
best = val2[0] - val2[1] + dp[u][0] + 1ll * w;
}
else
{
best += val1[0] - val1[1] + dp[u][0];
best += val2[0] - val2[1] + dp[u][0];
best -= dp[u][0];
best += 1ll * w;
}
dp[u][1] = max(dp[u][1], best);
}
B[1].update(in[u], out[u], max(dp[u][0], dp[u][1]) );
}
void solve()
{
cin >> n;
for(int i = 1, u, v; i <= n - 1; i ++)
{
cin >> u >> v;
o[u].push_back(v);
o[v].push_back(u);
}
dfs(1);
cin >> Q;
for(int i = 1, u, v, w; i <= Q; i ++)
{
cin >> u >> v >> w;
int par = lca(u, v);
qr[par].push_back({ u, v, w });
}
dfs2(1);
ll ans = 0;
for(int i = 1; i <= n; i ++) ans = max({ ans, dp[i][0], dp[i][1] });
cout << ans;
}
int main()
{
iof();
int nTest = 1;
// cin >> nTest;
while(nTest --) {
solve();
}
ctime();
return 0;
}
Compilation message
election_campaign.cpp: In function 'void iof()':
election_campaign.cpp:17:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen(Y8o".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
3 ms |
10772 KB |
Output is correct |
5 |
Correct |
55 ms |
21588 KB |
Output is correct |
6 |
Correct |
45 ms |
30856 KB |
Output is correct |
7 |
Correct |
66 ms |
27472 KB |
Output is correct |
8 |
Correct |
45 ms |
20572 KB |
Output is correct |
9 |
Correct |
61 ms |
25680 KB |
Output is correct |
10 |
Correct |
42 ms |
20308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10840 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
94 ms |
34184 KB |
Output is correct |
5 |
Correct |
96 ms |
34384 KB |
Output is correct |
6 |
Correct |
85 ms |
34132 KB |
Output is correct |
7 |
Correct |
93 ms |
34128 KB |
Output is correct |
8 |
Correct |
108 ms |
34128 KB |
Output is correct |
9 |
Correct |
94 ms |
34132 KB |
Output is correct |
10 |
Correct |
94 ms |
34180 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10840 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10844 KB |
Output is correct |
4 |
Correct |
94 ms |
34184 KB |
Output is correct |
5 |
Correct |
96 ms |
34384 KB |
Output is correct |
6 |
Correct |
85 ms |
34132 KB |
Output is correct |
7 |
Correct |
93 ms |
34128 KB |
Output is correct |
8 |
Correct |
108 ms |
34128 KB |
Output is correct |
9 |
Correct |
94 ms |
34132 KB |
Output is correct |
10 |
Correct |
94 ms |
34180 KB |
Output is correct |
11 |
Correct |
11 ms |
11612 KB |
Output is correct |
12 |
Correct |
94 ms |
34640 KB |
Output is correct |
13 |
Correct |
96 ms |
34344 KB |
Output is correct |
14 |
Correct |
87 ms |
34388 KB |
Output is correct |
15 |
Correct |
111 ms |
34388 KB |
Output is correct |
16 |
Correct |
86 ms |
34384 KB |
Output is correct |
17 |
Correct |
94 ms |
34420 KB |
Output is correct |
18 |
Correct |
95 ms |
34388 KB |
Output is correct |
19 |
Correct |
84 ms |
34384 KB |
Output is correct |
20 |
Correct |
98 ms |
34384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
24332 KB |
Output is correct |
2 |
Correct |
85 ms |
34256 KB |
Output is correct |
3 |
Correct |
145 ms |
30388 KB |
Output is correct |
4 |
Correct |
90 ms |
23304 KB |
Output is correct |
5 |
Correct |
119 ms |
29952 KB |
Output is correct |
6 |
Correct |
83 ms |
23160 KB |
Output is correct |
7 |
Correct |
139 ms |
29944 KB |
Output is correct |
8 |
Correct |
110 ms |
24540 KB |
Output is correct |
9 |
Correct |
89 ms |
34128 KB |
Output is correct |
10 |
Correct |
127 ms |
28428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
3 ms |
10772 KB |
Output is correct |
5 |
Correct |
55 ms |
21588 KB |
Output is correct |
6 |
Correct |
45 ms |
30856 KB |
Output is correct |
7 |
Correct |
66 ms |
27472 KB |
Output is correct |
8 |
Correct |
45 ms |
20572 KB |
Output is correct |
9 |
Correct |
61 ms |
25680 KB |
Output is correct |
10 |
Correct |
42 ms |
20308 KB |
Output is correct |
11 |
Correct |
3 ms |
10588 KB |
Output is correct |
12 |
Correct |
3 ms |
10844 KB |
Output is correct |
13 |
Correct |
3 ms |
11096 KB |
Output is correct |
14 |
Correct |
3 ms |
10680 KB |
Output is correct |
15 |
Correct |
3 ms |
10588 KB |
Output is correct |
16 |
Correct |
3 ms |
10728 KB |
Output is correct |
17 |
Correct |
3 ms |
10784 KB |
Output is correct |
18 |
Correct |
3 ms |
10840 KB |
Output is correct |
19 |
Correct |
3 ms |
10840 KB |
Output is correct |
20 |
Correct |
3 ms |
10844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10588 KB |
Output is correct |
2 |
Correct |
2 ms |
10588 KB |
Output is correct |
3 |
Correct |
2 ms |
10588 KB |
Output is correct |
4 |
Correct |
3 ms |
10772 KB |
Output is correct |
5 |
Correct |
55 ms |
21588 KB |
Output is correct |
6 |
Correct |
45 ms |
30856 KB |
Output is correct |
7 |
Correct |
66 ms |
27472 KB |
Output is correct |
8 |
Correct |
45 ms |
20572 KB |
Output is correct |
9 |
Correct |
61 ms |
25680 KB |
Output is correct |
10 |
Correct |
42 ms |
20308 KB |
Output is correct |
11 |
Correct |
2 ms |
10840 KB |
Output is correct |
12 |
Correct |
2 ms |
10588 KB |
Output is correct |
13 |
Correct |
2 ms |
10844 KB |
Output is correct |
14 |
Correct |
94 ms |
34184 KB |
Output is correct |
15 |
Correct |
96 ms |
34384 KB |
Output is correct |
16 |
Correct |
85 ms |
34132 KB |
Output is correct |
17 |
Correct |
93 ms |
34128 KB |
Output is correct |
18 |
Correct |
108 ms |
34128 KB |
Output is correct |
19 |
Correct |
94 ms |
34132 KB |
Output is correct |
20 |
Correct |
94 ms |
34180 KB |
Output is correct |
21 |
Correct |
11 ms |
11612 KB |
Output is correct |
22 |
Correct |
94 ms |
34640 KB |
Output is correct |
23 |
Correct |
96 ms |
34344 KB |
Output is correct |
24 |
Correct |
87 ms |
34388 KB |
Output is correct |
25 |
Correct |
111 ms |
34388 KB |
Output is correct |
26 |
Correct |
86 ms |
34384 KB |
Output is correct |
27 |
Correct |
94 ms |
34420 KB |
Output is correct |
28 |
Correct |
95 ms |
34388 KB |
Output is correct |
29 |
Correct |
84 ms |
34384 KB |
Output is correct |
30 |
Correct |
98 ms |
34384 KB |
Output is correct |
31 |
Correct |
110 ms |
24332 KB |
Output is correct |
32 |
Correct |
85 ms |
34256 KB |
Output is correct |
33 |
Correct |
145 ms |
30388 KB |
Output is correct |
34 |
Correct |
90 ms |
23304 KB |
Output is correct |
35 |
Correct |
119 ms |
29952 KB |
Output is correct |
36 |
Correct |
83 ms |
23160 KB |
Output is correct |
37 |
Correct |
139 ms |
29944 KB |
Output is correct |
38 |
Correct |
110 ms |
24540 KB |
Output is correct |
39 |
Correct |
89 ms |
34128 KB |
Output is correct |
40 |
Correct |
127 ms |
28428 KB |
Output is correct |
41 |
Correct |
3 ms |
10588 KB |
Output is correct |
42 |
Correct |
3 ms |
10844 KB |
Output is correct |
43 |
Correct |
3 ms |
11096 KB |
Output is correct |
44 |
Correct |
3 ms |
10680 KB |
Output is correct |
45 |
Correct |
3 ms |
10588 KB |
Output is correct |
46 |
Correct |
3 ms |
10728 KB |
Output is correct |
47 |
Correct |
3 ms |
10784 KB |
Output is correct |
48 |
Correct |
3 ms |
10840 KB |
Output is correct |
49 |
Correct |
3 ms |
10840 KB |
Output is correct |
50 |
Correct |
3 ms |
10844 KB |
Output is correct |
51 |
Correct |
124 ms |
24916 KB |
Output is correct |
52 |
Correct |
96 ms |
34384 KB |
Output is correct |
53 |
Correct |
152 ms |
28940 KB |
Output is correct |
54 |
Correct |
89 ms |
23436 KB |
Output is correct |
55 |
Correct |
106 ms |
24708 KB |
Output is correct |
56 |
Correct |
95 ms |
34336 KB |
Output is correct |
57 |
Correct |
123 ms |
29524 KB |
Output is correct |
58 |
Correct |
83 ms |
23564 KB |
Output is correct |
59 |
Correct |
111 ms |
24916 KB |
Output is correct |
60 |
Correct |
98 ms |
34276 KB |
Output is correct |
61 |
Correct |
134 ms |
29636 KB |
Output is correct |
62 |
Correct |
84 ms |
23340 KB |
Output is correct |
63 |
Correct |
99 ms |
24504 KB |
Output is correct |
64 |
Correct |
94 ms |
34308 KB |
Output is correct |
65 |
Correct |
147 ms |
29448 KB |
Output is correct |
66 |
Correct |
83 ms |
23544 KB |
Output is correct |
67 |
Correct |
107 ms |
24668 KB |
Output is correct |
68 |
Correct |
93 ms |
34384 KB |
Output is correct |
69 |
Correct |
120 ms |
28288 KB |
Output is correct |
70 |
Correct |
85 ms |
23604 KB |
Output is correct |