#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const ll inf = 1e16;
ll dp[N][2][2]; // node, par edge, bad path
vector<pair<int, int>> g[N];
int n, w[N];
void setup() {
for (int i = 1; i <= n; i++)
for (int x = 0; x < 2; x++)
for (int y = 0; y < 2; y++)
dp[i][x][y] = -inf;
}
void solve(int x, int fa, int uw) {
vector<int> ch;
for (auto& p : g[x]) {
int y = p.first;
if (y == fa) continue;
w[y] = p.second;
solve(y, x, w[y]);
ch.push_back(y);
}
if (ch.empty()) {
dp[x][0][0] = 0;
return;
}
// don't take x
{
vector<ll> cur(2, -inf);
cur[0] = 0;
for (int y : ch) {
vector<ll> ndp(2, -inf);
ndp[0] = max(ndp[0], cur[0] + dp[y][0][0]);
ndp[0] = max(ndp[0], cur[0] + dp[y][1][0]);
ndp[1] = max(ndp[1], cur[0] + dp[y][0][1]);
ndp[1] = max(ndp[1], cur[0] + dp[y][1][1]);
ndp[1] = max(ndp[1], cur[1] + dp[y][0][0]);
ndp[1] = max(ndp[1], cur[1] + dp[y][1][0]);
swap(cur, ndp);
}
dp[x][0][0] = max(dp[x][0][0], cur[0]);
dp[x][0][1] = max(dp[x][0][1], cur[1]);
}
// take x, from 2 down
{
vector<vector<ll>> cur(3, vector<ll>(2, -inf));
cur[0][0] = 0;
for (int y : ch) {
vector<vector<ll>> ndp(3, vector<ll>(2, -inf));
// don't take y
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 2; j++) {
ndp[i][j] = max(ndp[i][j], cur[i][j] + dp[y][0][0]);
ndp[i][j] = max(ndp[i][j], cur[i][j] + dp[y][1][0]);
}
}
// take y
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
for (int o = 0; o < 2; o++) {
if (j + o == 2) continue;
ndp[i + 1][j + o] = max(ndp[i + 1][j + o], cur[i][j] + dp[y][0][o] + w[y]);
}
}
}
swap(cur, ndp);
}
dp[x][0][1] = max({dp[x][0][1], cur[2][0], cur[2][1]});
}
// take x, from 1 down 1 up
{
vector<vector<ll>> cur(2, vector<ll>(2, -inf));
cur[0][0] = 0;
for (int y : ch) {
vector<vector<ll>> ndp(2, vector<ll>(2, -inf));
// don't take y
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
ndp[i][j] = max(ndp[i][j], cur[i][j] + dp[y][0][0]);
ndp[i][j] = max(ndp[i][j], cur[i][j] + dp[y][1][0]);
}
}
// take y
for (int i = 0; i < 1; i++) {
for (int j = 0; j < 2; j++) {
for (int o = 0; o < 2; o++) {
if (j + o == 2) continue;
ndp[i + 1][j + o] = max(ndp[i + 1][j + o], cur[i][j] + dp[y][0][o] + w[y]);
}
}
}
swap(cur, ndp);
}
dp[x][1][0] = max(dp[x][1][0], cur[1][0] + uw);
dp[x][1][1] = max(dp[x][1][1], cur[1][1] + uw);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a].push_back({b, c});
g[b].push_back({a, c});
}
setup();
solve(1, 1, -inf / 10);
printf("%lld\n", max(dp[1][0][0], dp[1][0][1]));
return 0;
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20
60
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
140
6
1 3 100
2 3 100
3 4 1
4 5 100
4 6 100
7
1 2 100
1 3 100
2 4 100
2 5 100
3 6 100
3 7 100
*/
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:120:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '-1000000000000000' to '1530494976' [-Woverflow]
120 | solve(1, 1, -inf / 10);
| ~~~~~^~~~
beads.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
beads.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | scanf("%d%d%d", &a, &b, &c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4900 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5016 KB |
Output is correct |
11 |
Correct |
3 ms |
5016 KB |
Output is correct |
12 |
Correct |
3 ms |
5016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4900 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5016 KB |
Output is correct |
11 |
Correct |
3 ms |
5016 KB |
Output is correct |
12 |
Correct |
3 ms |
5016 KB |
Output is correct |
13 |
Correct |
4 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
3 ms |
5020 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
5012 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4900 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5016 KB |
Output is correct |
11 |
Correct |
3 ms |
5016 KB |
Output is correct |
12 |
Correct |
3 ms |
5016 KB |
Output is correct |
13 |
Correct |
4 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
3 ms |
5020 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
5012 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5012 KB |
Output is correct |
23 |
Correct |
8 ms |
5332 KB |
Output is correct |
24 |
Correct |
8 ms |
5416 KB |
Output is correct |
25 |
Correct |
7 ms |
5332 KB |
Output is correct |
26 |
Correct |
11 ms |
5840 KB |
Output is correct |
27 |
Correct |
11 ms |
5844 KB |
Output is correct |
28 |
Correct |
9 ms |
5972 KB |
Output is correct |
29 |
Correct |
10 ms |
5952 KB |
Output is correct |
30 |
Correct |
10 ms |
5956 KB |
Output is correct |
31 |
Correct |
12 ms |
6764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4900 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5016 KB |
Output is correct |
11 |
Correct |
3 ms |
5016 KB |
Output is correct |
12 |
Correct |
3 ms |
5016 KB |
Output is correct |
13 |
Correct |
4 ms |
4948 KB |
Output is correct |
14 |
Correct |
3 ms |
5076 KB |
Output is correct |
15 |
Correct |
3 ms |
5020 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
5012 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5012 KB |
Output is correct |
23 |
Correct |
8 ms |
5332 KB |
Output is correct |
24 |
Correct |
8 ms |
5416 KB |
Output is correct |
25 |
Correct |
7 ms |
5332 KB |
Output is correct |
26 |
Correct |
11 ms |
5840 KB |
Output is correct |
27 |
Correct |
11 ms |
5844 KB |
Output is correct |
28 |
Correct |
9 ms |
5972 KB |
Output is correct |
29 |
Correct |
10 ms |
5952 KB |
Output is correct |
30 |
Correct |
10 ms |
5956 KB |
Output is correct |
31 |
Correct |
12 ms |
6764 KB |
Output is correct |
32 |
Correct |
52 ms |
9396 KB |
Output is correct |
33 |
Correct |
51 ms |
9396 KB |
Output is correct |
34 |
Correct |
51 ms |
9396 KB |
Output is correct |
35 |
Correct |
254 ms |
23060 KB |
Output is correct |
36 |
Correct |
284 ms |
23120 KB |
Output is correct |
37 |
Correct |
271 ms |
23028 KB |
Output is correct |
38 |
Correct |
174 ms |
25176 KB |
Output is correct |
39 |
Correct |
164 ms |
24440 KB |
Output is correct |
40 |
Correct |
213 ms |
24344 KB |
Output is correct |
41 |
Correct |
234 ms |
34132 KB |
Output is correct |