#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int INF = (int) 1e9 + 1e6;
const ll LINF = (ll) 1e18 + 1e9;
const ll MOD = (ll) 1e9 + 7;
#define sz(x) (int) (x).size()
#define mp(x, y) make_pair(x, y)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb(s, t, x) (int) (lower_bound(s, t, x) - s)
#define ub(s, t, x) (int) (upper_bound(s, t, x) - s)
#define rep(i, f, t) for (auto i = f; i < t; ++(i))
#define per(i, f, t) for (auto i = (f); i >= (t); --(i))
ll power(ll x, ll y, ll mod = MOD) {
if (y == 0) {
return 1;
}
if (y & 1) {
return power(x, y - 1, mod) * x % mod;
} else {
ll tmp = power(x, y / 2, mod);
return tmp * tmp % mod;
}
}
template<typename A, typename B> bool mini(A &x, const B &y) {
if (y < x) {
x = y;
return true;
}
return false;
}
template<typename A, typename B> bool maxi(A &x, const B &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
void add(ll &x, ll y) {
x += y;
if (x >= MOD) x -= MOD;
if (x < 0) x += MOD;
}
void run();
#define TASK ""
int main() {
#ifdef LOCAL
if (strlen(TASK) > 0) {
cerr << "Reminder: you are using file i/o, filename: " TASK "!" << endl << endl;
}
#endif
#ifndef LOCAL
if (strlen(TASK)) {
freopen(TASK ".in", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
cout << fixed << setprecision(12);
run();
return 0;
}
// == SOLUTION == //
const int N = (int) 1e5 + 123;
const int L = 20;
int n, m;
vector<int> g[N];
int depth[N];
int up[N][L];\
int tin[N], tout[N];
int f[N];
void add(int x, int y) {
x++;
for (; x < N; x += x & (-x)) f[x] += y;
}
int get(int r) {
int res = 0;
r++;
for (; r > 0; r -= r & (-r)) {
res += f[r];
}
return res;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
int tmr;
void precalc(int v, int p = -1) {
if (p == -1) {
rep(i, 0, L) up[v][i] = v;
} else {
up[v][0] = p;
rep(i, 1, L) up[v][i] = up[up[v][i - 1]][i - 1];
}
tin[v] = tmr++;
for (int u : g[v]) {
if (u == p) continue;
depth[u] = depth[v] + 1;
precalc(u, v);
}
tout[v] = tmr - 1;
}
bool test(int mask, int bit) {
return mask & (1 << bit);
}
int go(int v, int h) {
rep(i, 0, L) if (test(h, i)) v = up[v][i];
return v;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
u = go(u, depth[u] - depth[v]);
if (u == v) return u;
per(i, L - 1, 0) {
int uu = up[u][i];
int vv = up[v][i];
if (uu != vv) {
u = uu, v = vv;
}
}
return up[u][0];
}
struct Q {
int a, b, c;
};
int dp[N], sum[N];
vector<Q> what[N];
void solve(int v, int p = -1) {
for (int u : g[v]) {
if (u == p) continue;
solve(u, v);
sum[v] += dp[u];
}
maxi(dp[v], sum[v]);
for (auto &q : what[v]) {
int a = q.a;
int b = q.b;
if (a == v) {
swap(a, b);
}
if (b == v) {
int aa = go(a, depth[a] - depth[v] - 1);
maxi(dp[v], get(tin[a]) + sum[a] + sum[v] - dp[aa] + q.c);
} else {
int aa = go(a, depth[a] - depth[v] - 1);
int bb = go(b, depth[b] - depth[v] - 1);
maxi(dp[v], get(tin[a]) + sum[a] + get(tin[b]) + sum[b] + sum[v] - dp[aa] - dp[bb] + q.c);
}
}
for (int u : g[v]) {
if (u == p) continue;
add(tin[u], sum[v] - dp[u]);
add(tout[u] + 1, -(sum[v] - dp[u]));
}
}
void run() {
cin >> n;
rep(i, 0, n - 1) {
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
precalc(1);
cin >> m;
rep(i, 0, m) {
int u, v, c;
cin >> u >> v >> c;
int w = lca(u, v);
what[w].pb({u, v, c});
}
solve(1);
cout << dp[1] << "\n";
}
Compilation message
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(TASK ".in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
election_campaign.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen(TASK ".out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5112 KB |
Output is correct |
2 |
Correct |
5 ms |
5112 KB |
Output is correct |
3 |
Correct |
5 ms |
5172 KB |
Output is correct |
4 |
Correct |
7 ms |
5304 KB |
Output is correct |
5 |
Correct |
108 ms |
19520 KB |
Output is correct |
6 |
Correct |
69 ms |
28292 KB |
Output is correct |
7 |
Correct |
119 ms |
28292 KB |
Output is correct |
8 |
Correct |
81 ms |
28292 KB |
Output is correct |
9 |
Correct |
112 ms |
28292 KB |
Output is correct |
10 |
Correct |
94 ms |
28292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
28292 KB |
Output is correct |
2 |
Correct |
5 ms |
28292 KB |
Output is correct |
3 |
Correct |
6 ms |
28292 KB |
Output is correct |
4 |
Correct |
161 ms |
37752 KB |
Output is correct |
5 |
Correct |
167 ms |
40332 KB |
Output is correct |
6 |
Correct |
153 ms |
42824 KB |
Output is correct |
7 |
Correct |
167 ms |
45224 KB |
Output is correct |
8 |
Correct |
163 ms |
47744 KB |
Output is correct |
9 |
Correct |
234 ms |
50212 KB |
Output is correct |
10 |
Correct |
165 ms |
52672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
28292 KB |
Output is correct |
2 |
Correct |
5 ms |
28292 KB |
Output is correct |
3 |
Correct |
6 ms |
28292 KB |
Output is correct |
4 |
Correct |
161 ms |
37752 KB |
Output is correct |
5 |
Correct |
167 ms |
40332 KB |
Output is correct |
6 |
Correct |
153 ms |
42824 KB |
Output is correct |
7 |
Correct |
167 ms |
45224 KB |
Output is correct |
8 |
Correct |
163 ms |
47744 KB |
Output is correct |
9 |
Correct |
234 ms |
50212 KB |
Output is correct |
10 |
Correct |
165 ms |
52672 KB |
Output is correct |
11 |
Correct |
19 ms |
52672 KB |
Output is correct |
12 |
Correct |
187 ms |
55640 KB |
Output is correct |
13 |
Correct |
174 ms |
58380 KB |
Output is correct |
14 |
Correct |
148 ms |
61176 KB |
Output is correct |
15 |
Correct |
166 ms |
63840 KB |
Output is correct |
16 |
Correct |
190 ms |
66740 KB |
Output is correct |
17 |
Correct |
189 ms |
69408 KB |
Output is correct |
18 |
Correct |
178 ms |
72132 KB |
Output is correct |
19 |
Correct |
224 ms |
74992 KB |
Output is correct |
20 |
Correct |
177 ms |
77612 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
207 ms |
77612 KB |
Output is correct |
2 |
Correct |
156 ms |
82416 KB |
Output is correct |
3 |
Correct |
332 ms |
82416 KB |
Output is correct |
4 |
Correct |
149 ms |
82416 KB |
Output is correct |
5 |
Correct |
264 ms |
86596 KB |
Output is correct |
6 |
Correct |
159 ms |
86596 KB |
Output is correct |
7 |
Correct |
316 ms |
91220 KB |
Output is correct |
8 |
Correct |
213 ms |
91220 KB |
Output is correct |
9 |
Correct |
150 ms |
99916 KB |
Output is correct |
10 |
Correct |
305 ms |
99916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5112 KB |
Output is correct |
2 |
Correct |
5 ms |
5112 KB |
Output is correct |
3 |
Correct |
5 ms |
5172 KB |
Output is correct |
4 |
Correct |
7 ms |
5304 KB |
Output is correct |
5 |
Correct |
108 ms |
19520 KB |
Output is correct |
6 |
Correct |
69 ms |
28292 KB |
Output is correct |
7 |
Correct |
119 ms |
28292 KB |
Output is correct |
8 |
Correct |
81 ms |
28292 KB |
Output is correct |
9 |
Correct |
112 ms |
28292 KB |
Output is correct |
10 |
Correct |
94 ms |
28292 KB |
Output is correct |
11 |
Correct |
7 ms |
99916 KB |
Output is correct |
12 |
Correct |
7 ms |
99916 KB |
Output is correct |
13 |
Correct |
7 ms |
99916 KB |
Output is correct |
14 |
Correct |
6 ms |
99916 KB |
Output is correct |
15 |
Correct |
6 ms |
99916 KB |
Output is correct |
16 |
Correct |
7 ms |
99916 KB |
Output is correct |
17 |
Correct |
7 ms |
99916 KB |
Output is correct |
18 |
Correct |
7 ms |
99916 KB |
Output is correct |
19 |
Correct |
6 ms |
99916 KB |
Output is correct |
20 |
Correct |
6 ms |
99916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
5112 KB |
Output is correct |
2 |
Correct |
5 ms |
5112 KB |
Output is correct |
3 |
Correct |
5 ms |
5172 KB |
Output is correct |
4 |
Correct |
7 ms |
5304 KB |
Output is correct |
5 |
Correct |
108 ms |
19520 KB |
Output is correct |
6 |
Correct |
69 ms |
28292 KB |
Output is correct |
7 |
Correct |
119 ms |
28292 KB |
Output is correct |
8 |
Correct |
81 ms |
28292 KB |
Output is correct |
9 |
Correct |
112 ms |
28292 KB |
Output is correct |
10 |
Correct |
94 ms |
28292 KB |
Output is correct |
11 |
Correct |
5 ms |
28292 KB |
Output is correct |
12 |
Correct |
5 ms |
28292 KB |
Output is correct |
13 |
Correct |
6 ms |
28292 KB |
Output is correct |
14 |
Correct |
161 ms |
37752 KB |
Output is correct |
15 |
Correct |
167 ms |
40332 KB |
Output is correct |
16 |
Correct |
153 ms |
42824 KB |
Output is correct |
17 |
Correct |
167 ms |
45224 KB |
Output is correct |
18 |
Correct |
163 ms |
47744 KB |
Output is correct |
19 |
Correct |
234 ms |
50212 KB |
Output is correct |
20 |
Correct |
165 ms |
52672 KB |
Output is correct |
21 |
Correct |
19 ms |
52672 KB |
Output is correct |
22 |
Correct |
187 ms |
55640 KB |
Output is correct |
23 |
Correct |
174 ms |
58380 KB |
Output is correct |
24 |
Correct |
148 ms |
61176 KB |
Output is correct |
25 |
Correct |
166 ms |
63840 KB |
Output is correct |
26 |
Correct |
190 ms |
66740 KB |
Output is correct |
27 |
Correct |
189 ms |
69408 KB |
Output is correct |
28 |
Correct |
178 ms |
72132 KB |
Output is correct |
29 |
Correct |
224 ms |
74992 KB |
Output is correct |
30 |
Correct |
177 ms |
77612 KB |
Output is correct |
31 |
Correct |
207 ms |
77612 KB |
Output is correct |
32 |
Correct |
156 ms |
82416 KB |
Output is correct |
33 |
Correct |
332 ms |
82416 KB |
Output is correct |
34 |
Correct |
149 ms |
82416 KB |
Output is correct |
35 |
Correct |
264 ms |
86596 KB |
Output is correct |
36 |
Correct |
159 ms |
86596 KB |
Output is correct |
37 |
Correct |
316 ms |
91220 KB |
Output is correct |
38 |
Correct |
213 ms |
91220 KB |
Output is correct |
39 |
Correct |
150 ms |
99916 KB |
Output is correct |
40 |
Correct |
305 ms |
99916 KB |
Output is correct |
41 |
Correct |
7 ms |
99916 KB |
Output is correct |
42 |
Correct |
7 ms |
99916 KB |
Output is correct |
43 |
Correct |
7 ms |
99916 KB |
Output is correct |
44 |
Correct |
6 ms |
99916 KB |
Output is correct |
45 |
Correct |
6 ms |
99916 KB |
Output is correct |
46 |
Correct |
7 ms |
99916 KB |
Output is correct |
47 |
Correct |
7 ms |
99916 KB |
Output is correct |
48 |
Correct |
7 ms |
99916 KB |
Output is correct |
49 |
Correct |
6 ms |
99916 KB |
Output is correct |
50 |
Correct |
6 ms |
99916 KB |
Output is correct |
51 |
Correct |
207 ms |
99916 KB |
Output is correct |
52 |
Correct |
184 ms |
108116 KB |
Output is correct |
53 |
Correct |
311 ms |
108116 KB |
Output is correct |
54 |
Correct |
202 ms |
108116 KB |
Output is correct |
55 |
Correct |
216 ms |
108416 KB |
Output is correct |
56 |
Correct |
238 ms |
119044 KB |
Output is correct |
57 |
Correct |
243 ms |
119044 KB |
Output is correct |
58 |
Correct |
192 ms |
119044 KB |
Output is correct |
59 |
Correct |
220 ms |
119660 KB |
Output is correct |
60 |
Correct |
211 ms |
130064 KB |
Output is correct |
61 |
Correct |
328 ms |
130064 KB |
Output is correct |
62 |
Correct |
292 ms |
130064 KB |
Output is correct |
63 |
Correct |
301 ms |
130176 KB |
Output is correct |
64 |
Correct |
319 ms |
141060 KB |
Output is correct |
65 |
Correct |
377 ms |
141060 KB |
Output is correct |
66 |
Correct |
168 ms |
141060 KB |
Output is correct |
67 |
Correct |
260 ms |
141236 KB |
Output is correct |
68 |
Correct |
193 ms |
152060 KB |
Output is correct |
69 |
Correct |
256 ms |
152060 KB |
Output is correct |
70 |
Correct |
197 ms |
152060 KB |
Output is correct |