#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int) 1e5 + 7;
const int K = 17;
int n;
int m;
vector<int> g[N];
int tab[K][N];
int tin[N];
int tout[N];
int depth[N];
ll sum[N];
ll dp[N];
int t = 0;
struct Offer {
int x;
int y;
int cost;
};
vector<Offer> offers[N];
void dfs(int a, int p = 0) {
tin[a] = ++t;
depth[a] = depth[p] + 1;
tab[0][a] = p;
for (int k = 1; k < K; k++) {
tab[k][a] = tab[k - 1][tab[k - 1][a]];
}
for (auto &b : g[a]) {
if (b != p) {
dfs(b, a);
}
}
tout[a] = t;
}
int lca(int a, int b) {
if (depth[a] < depth[b]) {
swap(a, b);
}
for (int k = K - 1; k >= 0; k--) {
if (depth[b] + (1 << k) <= depth[a]) {
a = tab[k][a];
}
}
if (a == b) {
return a;
}
for (int k = K - 1; k >= 0; k--){
if (tab[k][a] != tab[k][b]) {
a = tab[k][a];
b = tab[k][b];
}
}
return tab[0][a];
}
ll aib[N];
void add(int i, int x) {
while (i < N) {
aib[i] += x;
i += i & (-i);
}
}
ll get(int i) {
int sol = 0;
while (i) {
sol += aib[i];
i -= i & (-i);
}
return sol;
}
void run(int a) {
for (auto &b : g[a]) {
if (b != tab[0][a]) {
run(b);
sum[a] += dp[b];
}
}
dp[a] = sum[a];
for (auto &i : offers[a]) {
ll now = get(tin[i.x]) + get(tin[i.y]) + sum[a] + i.cost;
dp[a] = max(dp[a], now);
}
add(tin[a], sum[a] - dp[a]);
add(tout[a] + 1, dp[a] - sum[a]);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
bool isHome;
isHome = true;
isHome = false;
if (isHome) {
freopen ("input", "r", stdin);
} else {
ios::sync_with_stdio(0); cin.tie(0);
}
cin >> n;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1);
cin >> m;
for (int i = 1; i <= m; i++) {
int x, y, cost;
cin >> x >> y >> cost;
offers[lca(x, y)].push_back({x, y, cost});
}
run(1);
cout << dp[1] << "\n";
return 0;
}
Compilation message
election_campaign.cpp: In function 'int main()':
election_campaign.cpp:107:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
107 | freopen ("input", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5160 KB |
Output is correct |
3 |
Correct |
3 ms |
5156 KB |
Output is correct |
4 |
Correct |
3 ms |
5204 KB |
Output is correct |
5 |
Correct |
57 ms |
19600 KB |
Output is correct |
6 |
Correct |
35 ms |
27228 KB |
Output is correct |
7 |
Correct |
65 ms |
24496 KB |
Output is correct |
8 |
Correct |
46 ms |
19152 KB |
Output is correct |
9 |
Correct |
55 ms |
22976 KB |
Output is correct |
10 |
Correct |
59 ms |
19204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5088 KB |
Output is correct |
3 |
Correct |
3 ms |
5332 KB |
Output is correct |
4 |
Correct |
80 ms |
30512 KB |
Output is correct |
5 |
Correct |
83 ms |
30492 KB |
Output is correct |
6 |
Correct |
71 ms |
30540 KB |
Output is correct |
7 |
Correct |
87 ms |
30516 KB |
Output is correct |
8 |
Correct |
81 ms |
30608 KB |
Output is correct |
9 |
Correct |
69 ms |
30540 KB |
Output is correct |
10 |
Correct |
80 ms |
30540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5088 KB |
Output is correct |
3 |
Correct |
3 ms |
5332 KB |
Output is correct |
4 |
Correct |
80 ms |
30512 KB |
Output is correct |
5 |
Correct |
83 ms |
30492 KB |
Output is correct |
6 |
Correct |
71 ms |
30540 KB |
Output is correct |
7 |
Correct |
87 ms |
30516 KB |
Output is correct |
8 |
Correct |
81 ms |
30608 KB |
Output is correct |
9 |
Correct |
69 ms |
30540 KB |
Output is correct |
10 |
Correct |
80 ms |
30540 KB |
Output is correct |
11 |
Correct |
9 ms |
6164 KB |
Output is correct |
12 |
Correct |
83 ms |
30864 KB |
Output is correct |
13 |
Correct |
84 ms |
30764 KB |
Output is correct |
14 |
Correct |
78 ms |
30832 KB |
Output is correct |
15 |
Correct |
82 ms |
30812 KB |
Output is correct |
16 |
Correct |
73 ms |
30800 KB |
Output is correct |
17 |
Correct |
85 ms |
30788 KB |
Output is correct |
18 |
Correct |
93 ms |
30780 KB |
Output is correct |
19 |
Correct |
79 ms |
30892 KB |
Output is correct |
20 |
Correct |
84 ms |
30796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
98 ms |
22344 KB |
Output is correct |
2 |
Correct |
70 ms |
30560 KB |
Output is correct |
3 |
Correct |
118 ms |
27476 KB |
Output is correct |
4 |
Correct |
75 ms |
22076 KB |
Output is correct |
5 |
Correct |
102 ms |
27000 KB |
Output is correct |
6 |
Correct |
83 ms |
22080 KB |
Output is correct |
7 |
Correct |
122 ms |
26748 KB |
Output is correct |
8 |
Correct |
99 ms |
22588 KB |
Output is correct |
9 |
Correct |
71 ms |
30612 KB |
Output is correct |
10 |
Correct |
144 ms |
25704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5160 KB |
Output is correct |
3 |
Correct |
3 ms |
5156 KB |
Output is correct |
4 |
Correct |
3 ms |
5204 KB |
Output is correct |
5 |
Correct |
57 ms |
19600 KB |
Output is correct |
6 |
Correct |
35 ms |
27228 KB |
Output is correct |
7 |
Correct |
65 ms |
24496 KB |
Output is correct |
8 |
Correct |
46 ms |
19152 KB |
Output is correct |
9 |
Correct |
55 ms |
22976 KB |
Output is correct |
10 |
Correct |
59 ms |
19204 KB |
Output is correct |
11 |
Correct |
3 ms |
5332 KB |
Output is correct |
12 |
Correct |
3 ms |
5296 KB |
Output is correct |
13 |
Correct |
3 ms |
5300 KB |
Output is correct |
14 |
Correct |
3 ms |
5332 KB |
Output is correct |
15 |
Correct |
3 ms |
5296 KB |
Output is correct |
16 |
Correct |
3 ms |
5332 KB |
Output is correct |
17 |
Correct |
3 ms |
5296 KB |
Output is correct |
18 |
Correct |
3 ms |
5300 KB |
Output is correct |
19 |
Correct |
3 ms |
5332 KB |
Output is correct |
20 |
Correct |
3 ms |
5332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5160 KB |
Output is correct |
3 |
Correct |
3 ms |
5156 KB |
Output is correct |
4 |
Correct |
3 ms |
5204 KB |
Output is correct |
5 |
Correct |
57 ms |
19600 KB |
Output is correct |
6 |
Correct |
35 ms |
27228 KB |
Output is correct |
7 |
Correct |
65 ms |
24496 KB |
Output is correct |
8 |
Correct |
46 ms |
19152 KB |
Output is correct |
9 |
Correct |
55 ms |
22976 KB |
Output is correct |
10 |
Correct |
59 ms |
19204 KB |
Output is correct |
11 |
Correct |
3 ms |
5076 KB |
Output is correct |
12 |
Correct |
3 ms |
5088 KB |
Output is correct |
13 |
Correct |
3 ms |
5332 KB |
Output is correct |
14 |
Correct |
80 ms |
30512 KB |
Output is correct |
15 |
Correct |
83 ms |
30492 KB |
Output is correct |
16 |
Correct |
71 ms |
30540 KB |
Output is correct |
17 |
Correct |
87 ms |
30516 KB |
Output is correct |
18 |
Correct |
81 ms |
30608 KB |
Output is correct |
19 |
Correct |
69 ms |
30540 KB |
Output is correct |
20 |
Correct |
80 ms |
30540 KB |
Output is correct |
21 |
Correct |
9 ms |
6164 KB |
Output is correct |
22 |
Correct |
83 ms |
30864 KB |
Output is correct |
23 |
Correct |
84 ms |
30764 KB |
Output is correct |
24 |
Correct |
78 ms |
30832 KB |
Output is correct |
25 |
Correct |
82 ms |
30812 KB |
Output is correct |
26 |
Correct |
73 ms |
30800 KB |
Output is correct |
27 |
Correct |
85 ms |
30788 KB |
Output is correct |
28 |
Correct |
93 ms |
30780 KB |
Output is correct |
29 |
Correct |
79 ms |
30892 KB |
Output is correct |
30 |
Correct |
84 ms |
30796 KB |
Output is correct |
31 |
Correct |
98 ms |
22344 KB |
Output is correct |
32 |
Correct |
70 ms |
30560 KB |
Output is correct |
33 |
Correct |
118 ms |
27476 KB |
Output is correct |
34 |
Correct |
75 ms |
22076 KB |
Output is correct |
35 |
Correct |
102 ms |
27000 KB |
Output is correct |
36 |
Correct |
83 ms |
22080 KB |
Output is correct |
37 |
Correct |
122 ms |
26748 KB |
Output is correct |
38 |
Correct |
99 ms |
22588 KB |
Output is correct |
39 |
Correct |
71 ms |
30612 KB |
Output is correct |
40 |
Correct |
144 ms |
25704 KB |
Output is correct |
41 |
Correct |
3 ms |
5332 KB |
Output is correct |
42 |
Correct |
3 ms |
5296 KB |
Output is correct |
43 |
Correct |
3 ms |
5300 KB |
Output is correct |
44 |
Correct |
3 ms |
5332 KB |
Output is correct |
45 |
Correct |
3 ms |
5296 KB |
Output is correct |
46 |
Correct |
3 ms |
5332 KB |
Output is correct |
47 |
Correct |
3 ms |
5296 KB |
Output is correct |
48 |
Correct |
3 ms |
5300 KB |
Output is correct |
49 |
Correct |
3 ms |
5332 KB |
Output is correct |
50 |
Correct |
3 ms |
5332 KB |
Output is correct |
51 |
Correct |
95 ms |
22952 KB |
Output is correct |
52 |
Correct |
83 ms |
30784 KB |
Output is correct |
53 |
Correct |
128 ms |
26064 KB |
Output is correct |
54 |
Correct |
68 ms |
22308 KB |
Output is correct |
55 |
Correct |
106 ms |
22724 KB |
Output is correct |
56 |
Correct |
91 ms |
30860 KB |
Output is correct |
57 |
Correct |
115 ms |
26960 KB |
Output is correct |
58 |
Correct |
76 ms |
22272 KB |
Output is correct |
59 |
Correct |
100 ms |
22964 KB |
Output is correct |
60 |
Correct |
83 ms |
30760 KB |
Output is correct |
61 |
Correct |
120 ms |
26948 KB |
Output is correct |
62 |
Correct |
76 ms |
22056 KB |
Output is correct |
63 |
Correct |
97 ms |
22556 KB |
Output is correct |
64 |
Correct |
84 ms |
30852 KB |
Output is correct |
65 |
Correct |
136 ms |
26760 KB |
Output is correct |
66 |
Correct |
71 ms |
22280 KB |
Output is correct |
67 |
Correct |
97 ms |
22608 KB |
Output is correct |
68 |
Correct |
84 ms |
30816 KB |
Output is correct |
69 |
Correct |
107 ms |
25664 KB |
Output is correct |
70 |
Correct |
74 ms |
22480 KB |
Output is correct |