#include<bits/stdc++.h>
#define oo 1000000000
#define maxn 200005
using namespace std;
typedef long long ll;
int n;
vector < pair < int, int > > g[maxn];
int dp[maxn][4];
void dfs(int u, int du) {
dp[u][0] = dp[u][1] = 0;
dp[u][2] = dp[u][3] = -oo;
for (auto i : g[u]) {
int v = i.first, w = i.second;
if (du == v) continue;
dfs(v, u);
int a = max(dp[u][0] + max(dp[v][1], dp[v][2] + w), dp[u][1] + dp[v][3] + w);
a = max(a, max(dp[u][2] + max(dp[v][0], dp[v][1]), dp[u][3] + dp[v][1]) + w);
a = max(a, dp[u][1] + max(dp[v][0], dp[v][1]));
int b = dp[u][1] + max(dp[v][1], dp[v][2] + w);
int c = max(dp[u][2] + max(dp[v][2] + w, dp[v][1]), dp[u][1] + dp[v][1] + w);
int d = max(dp[u][3] + max(dp[v][2] + w, dp[v][1]), dp[u][1] + max(dp[v][0], dp[v][1]) + w);
dp[u][0] = a;
dp[u][1] = b;
dp[u][2] = c;
dp[u][3] = d;
//if (u == 1) cerr << a << ' ' << b << ' ' << c << ' ' << d << '\n';
}
}
int main(){
#define TASK "ABC"
//freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v, c;
cin >> u >> v >> c;
g[u].push_back({v, c});
g[v].push_back({u, c});
}
int root = 1;
dfs(root, root);
//cerr << dp[8][1] << '\n';
cout << max(dp[root][0], dp[root][1]);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
4992 KB |
Output is correct |
2 |
Correct |
8 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
8 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
4992 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
4992 KB |
Output is correct |
2 |
Correct |
8 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
8 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
4992 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
10 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
8 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
4992 KB |
Output is correct |
2 |
Correct |
8 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
8 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
4992 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
10 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
8 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
23 |
Correct |
11 ms |
5376 KB |
Output is correct |
24 |
Correct |
10 ms |
5376 KB |
Output is correct |
25 |
Correct |
10 ms |
5376 KB |
Output is correct |
26 |
Correct |
12 ms |
5760 KB |
Output is correct |
27 |
Correct |
12 ms |
5760 KB |
Output is correct |
28 |
Correct |
11 ms |
5760 KB |
Output is correct |
29 |
Correct |
11 ms |
5760 KB |
Output is correct |
30 |
Correct |
12 ms |
5760 KB |
Output is correct |
31 |
Correct |
12 ms |
6016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
4992 KB |
Output is correct |
2 |
Correct |
8 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
8 ms |
4992 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
4992 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
5120 KB |
Output is correct |
11 |
Correct |
7 ms |
4992 KB |
Output is correct |
12 |
Correct |
7 ms |
5120 KB |
Output is correct |
13 |
Correct |
7 ms |
5120 KB |
Output is correct |
14 |
Correct |
7 ms |
4992 KB |
Output is correct |
15 |
Correct |
10 ms |
4992 KB |
Output is correct |
16 |
Correct |
8 ms |
4992 KB |
Output is correct |
17 |
Correct |
7 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
5120 KB |
Output is correct |
19 |
Correct |
8 ms |
4992 KB |
Output is correct |
20 |
Correct |
7 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
23 |
Correct |
11 ms |
5376 KB |
Output is correct |
24 |
Correct |
10 ms |
5376 KB |
Output is correct |
25 |
Correct |
10 ms |
5376 KB |
Output is correct |
26 |
Correct |
12 ms |
5760 KB |
Output is correct |
27 |
Correct |
12 ms |
5760 KB |
Output is correct |
28 |
Correct |
11 ms |
5760 KB |
Output is correct |
29 |
Correct |
11 ms |
5760 KB |
Output is correct |
30 |
Correct |
12 ms |
5760 KB |
Output is correct |
31 |
Correct |
12 ms |
6016 KB |
Output is correct |
32 |
Correct |
36 ms |
8440 KB |
Output is correct |
33 |
Correct |
43 ms |
8440 KB |
Output is correct |
34 |
Correct |
39 ms |
8440 KB |
Output is correct |
35 |
Correct |
187 ms |
19192 KB |
Output is correct |
36 |
Correct |
188 ms |
19192 KB |
Output is correct |
37 |
Correct |
193 ms |
19192 KB |
Output is correct |
38 |
Correct |
134 ms |
19556 KB |
Output is correct |
39 |
Correct |
137 ms |
19544 KB |
Output is correct |
40 |
Correct |
177 ms |
19428 KB |
Output is correct |
41 |
Correct |
188 ms |
22636 KB |
Output is correct |