#include <bits/stdc++.h>
#define ii pair < int , int >
#define fi first
#define se second
using namespace std;
const int maxn = 200010;
const int inf = 0x3f3f3f3f;
vector < ii > g[maxn];
int dp[maxn][3] , f[maxn];
void DFS(int u,int p,int wp) {
for (auto v : g[u])
if (v.fi != p)
DFS(v.fi , u , v.se);
for (auto v : g[u])
if (v.fi != p)
dp[u][0] += max(dp[v.fi][0] , dp[v.fi][1]);
for (auto v : g[u])
if (v.fi != p)
dp[u][1] = max(dp[u][1] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][0] + wp + v.se);
dp[u][2] = dp[u][0];
int ma1 , ma2;
ma1 = ma2 = -inf;
for (auto v : g[u])
if (v.fi != p) {
int cur = dp[v.fi][0] - max(dp[v.fi][0] , dp[v.fi][1]) + v.se;
if (cur > ma1) {
ma2 = ma1;
ma1 = cur;
} else ma2 = max(ma2 , cur);
}
for (auto v : g[u])
if (v.fi != p) {
int cur = ma1;
if (cur == dp[v.fi][0] - max(dp[v.fi][0] , dp[v.fi][1]) + v.se) cur = ma2;
dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][2]);
dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + dp[v.fi][2] + cur + v.se);
dp[u][2] = max(dp[u][2] , dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]) + f[v.fi] + v.se);
}
f[u] = -inf;
for (auto v : g[u])
if (v.fi != p)
f[u] = max(f[u] , dp[v.fi][2] + v.se + dp[u][0] - max(dp[v.fi][0] , dp[v.fi][1]));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
for (int i = 1 ; i < n ; ++i) {
int u , v , w;
cin >> u >> v >> w;
g[u].emplace_back(v , w);
g[v].emplace_back(u , w);
}
DFS(1 , 0 , 0);
cout << dp[1][2];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
2 ms |
4940 KB |
Output is correct |
4 |
Correct |
2 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
2 ms |
5012 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
2 ms |
4940 KB |
Output is correct |
9 |
Correct |
2 ms |
4940 KB |
Output is correct |
10 |
Correct |
2 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
2 ms |
4940 KB |
Output is correct |
4 |
Correct |
2 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
2 ms |
5012 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
2 ms |
4940 KB |
Output is correct |
9 |
Correct |
2 ms |
4940 KB |
Output is correct |
10 |
Correct |
2 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4992 KB |
Output is correct |
13 |
Correct |
3 ms |
5016 KB |
Output is correct |
14 |
Correct |
2 ms |
4940 KB |
Output is correct |
15 |
Correct |
2 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
5016 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
2 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
3 ms |
4940 KB |
Output is correct |
22 |
Correct |
3 ms |
4932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
2 ms |
4940 KB |
Output is correct |
4 |
Correct |
2 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
2 ms |
5012 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
2 ms |
4940 KB |
Output is correct |
9 |
Correct |
2 ms |
4940 KB |
Output is correct |
10 |
Correct |
2 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4992 KB |
Output is correct |
13 |
Correct |
3 ms |
5016 KB |
Output is correct |
14 |
Correct |
2 ms |
4940 KB |
Output is correct |
15 |
Correct |
2 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
5016 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
2 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
3 ms |
4940 KB |
Output is correct |
22 |
Correct |
3 ms |
4932 KB |
Output is correct |
23 |
Correct |
5 ms |
5324 KB |
Output is correct |
24 |
Correct |
5 ms |
5324 KB |
Output is correct |
25 |
Correct |
5 ms |
5324 KB |
Output is correct |
26 |
Correct |
8 ms |
5672 KB |
Output is correct |
27 |
Correct |
7 ms |
5688 KB |
Output is correct |
28 |
Correct |
6 ms |
5696 KB |
Output is correct |
29 |
Correct |
7 ms |
5708 KB |
Output is correct |
30 |
Correct |
6 ms |
5708 KB |
Output is correct |
31 |
Correct |
7 ms |
5964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4940 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
2 ms |
4940 KB |
Output is correct |
4 |
Correct |
2 ms |
4940 KB |
Output is correct |
5 |
Correct |
3 ms |
4940 KB |
Output is correct |
6 |
Correct |
2 ms |
5012 KB |
Output is correct |
7 |
Correct |
2 ms |
4940 KB |
Output is correct |
8 |
Correct |
2 ms |
4940 KB |
Output is correct |
9 |
Correct |
2 ms |
4940 KB |
Output is correct |
10 |
Correct |
2 ms |
4940 KB |
Output is correct |
11 |
Correct |
3 ms |
4940 KB |
Output is correct |
12 |
Correct |
3 ms |
4992 KB |
Output is correct |
13 |
Correct |
3 ms |
5016 KB |
Output is correct |
14 |
Correct |
2 ms |
4940 KB |
Output is correct |
15 |
Correct |
2 ms |
4940 KB |
Output is correct |
16 |
Correct |
3 ms |
5016 KB |
Output is correct |
17 |
Correct |
3 ms |
4940 KB |
Output is correct |
18 |
Correct |
2 ms |
4940 KB |
Output is correct |
19 |
Correct |
3 ms |
4940 KB |
Output is correct |
20 |
Correct |
3 ms |
4940 KB |
Output is correct |
21 |
Correct |
3 ms |
4940 KB |
Output is correct |
22 |
Correct |
3 ms |
4932 KB |
Output is correct |
23 |
Correct |
5 ms |
5324 KB |
Output is correct |
24 |
Correct |
5 ms |
5324 KB |
Output is correct |
25 |
Correct |
5 ms |
5324 KB |
Output is correct |
26 |
Correct |
8 ms |
5672 KB |
Output is correct |
27 |
Correct |
7 ms |
5688 KB |
Output is correct |
28 |
Correct |
6 ms |
5696 KB |
Output is correct |
29 |
Correct |
7 ms |
5708 KB |
Output is correct |
30 |
Correct |
6 ms |
5708 KB |
Output is correct |
31 |
Correct |
7 ms |
5964 KB |
Output is correct |
32 |
Correct |
25 ms |
7824 KB |
Output is correct |
33 |
Correct |
24 ms |
7836 KB |
Output is correct |
34 |
Correct |
27 ms |
7876 KB |
Output is correct |
35 |
Correct |
137 ms |
15716 KB |
Output is correct |
36 |
Correct |
167 ms |
15792 KB |
Output is correct |
37 |
Correct |
139 ms |
15740 KB |
Output is correct |
38 |
Correct |
92 ms |
16032 KB |
Output is correct |
39 |
Correct |
93 ms |
16112 KB |
Output is correct |
40 |
Correct |
103 ms |
16028 KB |
Output is correct |
41 |
Correct |
137 ms |
19620 KB |
Output is correct |