#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax =500001;
/*
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
*/
ll dp[nmax][2][2];
ll val[nmax];
vector <vector <pii> > g(nmax);
void dfs(int v, int e = -1){
ll mx = -1e9;
pair<pll, pll> mx1;
pair<pll, pll> mx2;
pair<pll, pll> mx3, mx4;
mx1 = mx2 = mx3 = mx4 = {{mx, mx}, {mx, mx}};
ll MX = -1e9;
ll MMX = -1e9;
for(auto ed : g[v]){
int to = ed.f;
ll len = ed.s;
if(to == e) continue;
val[to] = len;
dfs(to, v);
ll y = max(dp[to][1][0], dp[to][0][0]);
dp[v][0][0] += y;
mx = max(mx, dp[to][0][0] - y + val[to]);
ll z = dp[to][0][1] - y + val[to];
mx1.s = max(mx1.s, {z, to});
if(mx1.f < mx1.s)
swap(mx1.f, mx1.s);
z = dp[to][0][0] - y + val[to];
mx2.s = max(mx2.s, {z, to});
if(mx2.f < mx2.s)
swap(mx2.f, mx2.s);
MX = max(MX, dp[to][0][1] - y + val[to]);
MMX = max(MMX, max(dp[to][0][1], dp[to][1][1]) - y);
}
dp[v][1][0] = max(dp[v][1][0], mx + dp[v][0][0] + val[v]);
if(mx1.f.s == mx2.f.s){
dp[v][0][1] = dp[v][0][0] + max(mx1.f.f + mx2.s.f, mx1.s.f + mx2.f.f);
}
else dp[v][0][1] = max(dp[v][0][1], dp[v][0][0] + mx1.f.f + mx2.f.f);
dp[v][1][1] = dp[v][0][0] + MX + val[v];
dp[v][0][1] = max(dp[v][0][1], dp[v][0][0]);
dp[v][0][1] = max(dp[v][0][1], dp[v][0][0] + MMX);
dp[v][1][1] = max(dp[v][1][1], dp[v][1][0]);
}
int32_t main() {
int n; cin >> n;
val[1] = -1e9;
for(int i = 1; i < n; i++){
int u, v, c; cin >> u >> v >> c;
g[u].pb({v, c});
g[v].pb({u, c});
}
dfs(1);
cout << max(dp[1][0][1], dp[1][0][0]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
11988 KB |
Output is correct |
3 |
Correct |
8 ms |
11984 KB |
Output is correct |
4 |
Correct |
7 ms |
12060 KB |
Output is correct |
5 |
Correct |
7 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11980 KB |
Output is correct |
10 |
Correct |
6 ms |
12044 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
11988 KB |
Output is correct |
3 |
Correct |
8 ms |
11984 KB |
Output is correct |
4 |
Correct |
7 ms |
12060 KB |
Output is correct |
5 |
Correct |
7 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11980 KB |
Output is correct |
10 |
Correct |
6 ms |
12044 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12068 KB |
Output is correct |
13 |
Correct |
7 ms |
11984 KB |
Output is correct |
14 |
Correct |
7 ms |
12076 KB |
Output is correct |
15 |
Correct |
7 ms |
12056 KB |
Output is correct |
16 |
Correct |
7 ms |
12068 KB |
Output is correct |
17 |
Correct |
6 ms |
12040 KB |
Output is correct |
18 |
Correct |
7 ms |
11988 KB |
Output is correct |
19 |
Correct |
6 ms |
12084 KB |
Output is correct |
20 |
Correct |
6 ms |
12060 KB |
Output is correct |
21 |
Correct |
6 ms |
11988 KB |
Output is correct |
22 |
Correct |
6 ms |
11988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
11988 KB |
Output is correct |
3 |
Correct |
8 ms |
11984 KB |
Output is correct |
4 |
Correct |
7 ms |
12060 KB |
Output is correct |
5 |
Correct |
7 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11980 KB |
Output is correct |
10 |
Correct |
6 ms |
12044 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12068 KB |
Output is correct |
13 |
Correct |
7 ms |
11984 KB |
Output is correct |
14 |
Correct |
7 ms |
12076 KB |
Output is correct |
15 |
Correct |
7 ms |
12056 KB |
Output is correct |
16 |
Correct |
7 ms |
12068 KB |
Output is correct |
17 |
Correct |
6 ms |
12040 KB |
Output is correct |
18 |
Correct |
7 ms |
11988 KB |
Output is correct |
19 |
Correct |
6 ms |
12084 KB |
Output is correct |
20 |
Correct |
6 ms |
12060 KB |
Output is correct |
21 |
Correct |
6 ms |
11988 KB |
Output is correct |
22 |
Correct |
6 ms |
11988 KB |
Output is correct |
23 |
Correct |
11 ms |
12500 KB |
Output is correct |
24 |
Correct |
10 ms |
12456 KB |
Output is correct |
25 |
Correct |
10 ms |
12500 KB |
Output is correct |
26 |
Correct |
15 ms |
12968 KB |
Output is correct |
27 |
Correct |
19 ms |
13012 KB |
Output is correct |
28 |
Correct |
18 ms |
13016 KB |
Output is correct |
29 |
Correct |
19 ms |
12884 KB |
Output is correct |
30 |
Correct |
14 ms |
12968 KB |
Output is correct |
31 |
Correct |
15 ms |
13652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11988 KB |
Output is correct |
2 |
Correct |
7 ms |
11988 KB |
Output is correct |
3 |
Correct |
8 ms |
11984 KB |
Output is correct |
4 |
Correct |
7 ms |
12060 KB |
Output is correct |
5 |
Correct |
7 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11980 KB |
Output is correct |
10 |
Correct |
6 ms |
12044 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12068 KB |
Output is correct |
13 |
Correct |
7 ms |
11984 KB |
Output is correct |
14 |
Correct |
7 ms |
12076 KB |
Output is correct |
15 |
Correct |
7 ms |
12056 KB |
Output is correct |
16 |
Correct |
7 ms |
12068 KB |
Output is correct |
17 |
Correct |
6 ms |
12040 KB |
Output is correct |
18 |
Correct |
7 ms |
11988 KB |
Output is correct |
19 |
Correct |
6 ms |
12084 KB |
Output is correct |
20 |
Correct |
6 ms |
12060 KB |
Output is correct |
21 |
Correct |
6 ms |
11988 KB |
Output is correct |
22 |
Correct |
6 ms |
11988 KB |
Output is correct |
23 |
Correct |
11 ms |
12500 KB |
Output is correct |
24 |
Correct |
10 ms |
12456 KB |
Output is correct |
25 |
Correct |
10 ms |
12500 KB |
Output is correct |
26 |
Correct |
15 ms |
12968 KB |
Output is correct |
27 |
Correct |
19 ms |
13012 KB |
Output is correct |
28 |
Correct |
18 ms |
13016 KB |
Output is correct |
29 |
Correct |
19 ms |
12884 KB |
Output is correct |
30 |
Correct |
14 ms |
12968 KB |
Output is correct |
31 |
Correct |
15 ms |
13652 KB |
Output is correct |
32 |
Correct |
55 ms |
16588 KB |
Output is correct |
33 |
Correct |
49 ms |
16584 KB |
Output is correct |
34 |
Correct |
52 ms |
16532 KB |
Output is correct |
35 |
Correct |
304 ms |
30764 KB |
Output is correct |
36 |
Correct |
276 ms |
30772 KB |
Output is correct |
37 |
Correct |
263 ms |
30784 KB |
Output is correct |
38 |
Correct |
222 ms |
31208 KB |
Output is correct |
39 |
Correct |
212 ms |
31144 KB |
Output is correct |
40 |
Correct |
212 ms |
31172 KB |
Output is correct |
41 |
Correct |
251 ms |
39860 KB |
Output is correct |