#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
const int MXN = 2e5, INF = 1e9;
vector<array<int, 2>> dp;
vector<vector<array<int, 2>>> adj;
int n, ans = 0;
void dfs(int p, int parent, int pe=0) {
dp[p] = {0, 0};
int v = 0;
for (auto i: adj[p]) if (i[0] != parent) {
dfs(i[0], p, i[1]);
v = max(v, -dp[i[0]][0] + dp[i[0]][1] + i[1] + pe);
dp[p][1] += dp[i[0]][0];
}
dp[p][0] = dp[p][1] + (p == parent ? 0 : v);
}
void reroot(int p, int parent) {
array<int, 2> opt = {-INF, -INF}, pre = dp[p];
if (parent != p) dp[p][1] += dp[parent][0];
for (auto i: adj[p]) {
int temp = -dp[i[0]][0] + dp[i[0]][1] + i[1];
if (temp >= opt[0]) {
swap(opt[0], opt[1]);
opt[0] = temp;
} else if (temp > opt[1]) opt[1] = temp;
}
ans = max(ans, dp[p][1]);
for (auto i: adj[p]) if (i[0] != parent) {
dp[p][1] -= dp[i[0]][0];
dp[p][0] = dp[p][1];
int temp = -dp[i[0]][0] + dp[i[0]][1] + i[1];
if (temp == opt[0]) dp[p][0] += max(opt[1]+i[1], 0);
else dp[p][0] += max(opt[0]+i[1], 0);
reroot(i[0], p);
dp[p][1] += dp[i[0]][0];
}
dp[p] = pre;
}
int main() {
#ifdef mlocal
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
dp.resize(n); adj.resize(n);
for_(i, 0, n-1) {
int a, b, w; cin >> a >> b >> w;
a -= 1; b -= 1;
adj[a].push_back({b, w}); adj[b].push_back({a, w});
}
dfs(0, 0, 0);
reroot(0, 0);
cout << ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
3 ms |
620 KB |
Output is correct |
24 |
Correct |
3 ms |
620 KB |
Output is correct |
25 |
Correct |
3 ms |
620 KB |
Output is correct |
26 |
Correct |
6 ms |
1004 KB |
Output is correct |
27 |
Correct |
7 ms |
1004 KB |
Output is correct |
28 |
Correct |
5 ms |
1132 KB |
Output is correct |
29 |
Correct |
5 ms |
1004 KB |
Output is correct |
30 |
Correct |
5 ms |
1004 KB |
Output is correct |
31 |
Correct |
6 ms |
1388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
0 ms |
364 KB |
Output is correct |
10 |
Correct |
0 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
364 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
384 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
3 ms |
620 KB |
Output is correct |
24 |
Correct |
3 ms |
620 KB |
Output is correct |
25 |
Correct |
3 ms |
620 KB |
Output is correct |
26 |
Correct |
6 ms |
1004 KB |
Output is correct |
27 |
Correct |
7 ms |
1004 KB |
Output is correct |
28 |
Correct |
5 ms |
1132 KB |
Output is correct |
29 |
Correct |
5 ms |
1004 KB |
Output is correct |
30 |
Correct |
5 ms |
1004 KB |
Output is correct |
31 |
Correct |
6 ms |
1388 KB |
Output is correct |
32 |
Correct |
29 ms |
3820 KB |
Output is correct |
33 |
Correct |
29 ms |
3820 KB |
Output is correct |
34 |
Correct |
34 ms |
3820 KB |
Output is correct |
35 |
Correct |
222 ms |
14212 KB |
Output is correct |
36 |
Correct |
228 ms |
14060 KB |
Output is correct |
37 |
Correct |
224 ms |
14060 KB |
Output is correct |
38 |
Correct |
141 ms |
14432 KB |
Output is correct |
39 |
Correct |
146 ms |
14416 KB |
Output is correct |
40 |
Correct |
154 ms |
14292 KB |
Output is correct |
41 |
Correct |
196 ms |
18016 KB |
Output is correct |