#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
const int MAX = 200005;
typedef pair<int, int> pii;
vector<pii> g[MAX];
int dp[MAX][2][2];
int max(int a, int b, int c) { return max(max(a, b), c); }
int max(int a, int b, int c, int d) { return max(max(a, b), max(c, d)); }
void dfs(int u, int p=-1, int len=-1) {
for (pii i : g[u]) {
if (i.f == p) { continue; }
dfs(i.f, u, i.s);
}
int sum = 0, sum2 = 0;
vector<pii> val0, val1;
for (pii i : g[u]) {
if (i.f == p) { continue; }
sum += max(dp[i.f][0][0], dp[i.f][1][0]);
val0.push_back({max(dp[i.f][0][0], dp[i.f][1][0]) - dp[i.f][0][0] - i.s, i.f});
val1.push_back({max(dp[i.f][0][0], dp[i.f][1][0]) - dp[i.f][0][1] - i.s, i.f});
}
sort(val0.begin(), val0.end());
sort(val1.begin(), val1.end());
for (int i=0; i<min(2, (int)val0.size()); i++) {
for (int j=0; j<min(2, (int)val1.size()); j++) {
if (val0[i].s != val1[j].s) {
dp[u][0][1] = max(dp[u][0][1], sum - val0[i].f - val1[j].f);
}
}
}
if (val0.size() >= 2) {
dp[u][0][1] = max(dp[u][0][1], sum - val0[0].f - val0[1].f);
}
if (p != -1) {
for (pii i : g[u]) {
if (i.f == p) { continue; }
dp[u][1][0] = max(dp[u][1][0], len + sum - max(dp[i.f][0][0], dp[i.f][1][0]) + dp[i.f][0][0] + i.s);
dp[u][1][1] = max(dp[u][1][1], len + sum - max(dp[i.f][0][0], dp[i.f][1][0]) + dp[i.f][0][1] + i.s);
}
}
dp[u][0][0] = sum;
for (pii i : g[u]) {
if (i.f == p) { continue; }
dp[u][0][1] = max(dp[u][0][1], sum - max(dp[i.f][0][0], dp[i.f][1][0]) + max(dp[i.f][0][1], dp[i.f][1][1]));
}
// cout << u << " " << dp[u][0][0] << " " << dp[u][0][1] << " " << dp[u][1][0] << " " << dp[u][1][1] << endl;
}
int main() {
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
int n; scanf("%d", &n);
for (int i=0; i<n-1; i++) {
int u, v, w; scanf("%d %d %d", &u, &v, &w);
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs(1);
printf("%d\n", max(dp[1][0][0], dp[1][0][1], dp[1][1][0], dp[1][1][1]));
}
Compilation message
beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:20:15: warning: unused variable 'sum2' [-Wunused-variable]
int sum = 0, sum2 = 0;
^~~~
beads.cpp: In function 'int main()':
beads.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n; scanf("%d", &n);
~~~~~^~~~~~~~~~
beads.cpp:60:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v, w; scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5004 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
12 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5004 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
12 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5004 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
12 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
23 |
Correct |
9 ms |
5376 KB |
Output is correct |
24 |
Correct |
8 ms |
5248 KB |
Output is correct |
25 |
Correct |
9 ms |
5300 KB |
Output is correct |
26 |
Correct |
13 ms |
5476 KB |
Output is correct |
27 |
Correct |
12 ms |
5504 KB |
Output is correct |
28 |
Correct |
13 ms |
6016 KB |
Output is correct |
29 |
Correct |
12 ms |
5632 KB |
Output is correct |
30 |
Correct |
13 ms |
5632 KB |
Output is correct |
31 |
Correct |
13 ms |
6400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5004 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
12 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
5 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
4992 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
6 ms |
5120 KB |
Output is correct |
23 |
Correct |
9 ms |
5376 KB |
Output is correct |
24 |
Correct |
8 ms |
5248 KB |
Output is correct |
25 |
Correct |
9 ms |
5300 KB |
Output is correct |
26 |
Correct |
13 ms |
5476 KB |
Output is correct |
27 |
Correct |
12 ms |
5504 KB |
Output is correct |
28 |
Correct |
13 ms |
6016 KB |
Output is correct |
29 |
Correct |
12 ms |
5632 KB |
Output is correct |
30 |
Correct |
13 ms |
5632 KB |
Output is correct |
31 |
Correct |
13 ms |
6400 KB |
Output is correct |
32 |
Correct |
42 ms |
7748 KB |
Output is correct |
33 |
Correct |
45 ms |
7808 KB |
Output is correct |
34 |
Correct |
44 ms |
7760 KB |
Output is correct |
35 |
Correct |
232 ms |
15584 KB |
Output is correct |
36 |
Correct |
236 ms |
15620 KB |
Output is correct |
37 |
Correct |
238 ms |
15608 KB |
Output is correct |
38 |
Correct |
214 ms |
20836 KB |
Output is correct |
39 |
Correct |
192 ms |
18688 KB |
Output is correct |
40 |
Correct |
211 ms |
17256 KB |
Output is correct |
41 |
Correct |
249 ms |
26220 KB |
Output is correct |