#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cassert>
using namespace std;
#define int long long
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define _1 first
#define _2 second
#define pb push_back
//#define INF 2100000000
#define INF (1LL<<40)
int N;
vector<P> G[200000];
P dp[200000][3];
void update(int x, int v, int s) {
if (P(v, s) > dp[x][1]) dp[x][2] = dp[x][1], dp[x][1] = P(v, s);
else if (P(v, s) > dp[x][2]) dp[x][2] = P(v, s);
}
int get(int x, int s=-2) { return dp[x][1+(dp[x][1]._2==s)]._1; }
void dfs(int x, int p) {
dp[x][0] = P(0, -1);
dp[x][1] = P(-INF, -1);
dp[x][2] = P(-INF, -1);
for (P pp : G[x]) if (pp._1 != p) {
int t = pp._1, len = pp._2;
dfs(t, x);
int v = max(dp[t][0]._1, dp[t][1]._1+len);
dp[x][0]._1 += v;
}
for (P pp : G[x]) if (pp._1 != p) {
int t = pp._1, len = pp._2;
int v = max(dp[t][0]._1, dp[t][1]._1+len);
update(x, dp[x][0]._1-v + dp[t][0]._1+len, t);
}
}
void dfs2(int x, int p, int plen, int diff) {
if (p != -1) {
int pv = max(plen + get(p, x) - diff, dp[p][0]._1 - diff);
for (int k=1; k<=2; k++) if (dp[x][k]._1 != -INF) dp[x][k]._1 += pv;
update(x, dp[x][0]._1 + plen + dp[p][0]._1 - diff, p);
int old =dp[x][0]._1;
dp[x][0]._1 += pv;
}
for (P pp : G[x]) if (pp._1 != p) {
int t = pp._1, len = pp._2;
dfs2(t, x, len, max(dp[t][0]._1, dp[t][1]._1+len));
}
}
signed main() {
cin >> N;
rep(i, N-1) {
int a, b, c;
cin >> a >> b >> c;
a--, b--;
G[a].pb(P(b, c));
G[b].pb(P(a, c));
}
dfs(0, -1);
dfs2(0, -1, 0, 0);
int m = 0;
rep(i, N) m = max(m, dp[i][0]._1);
cout << m << "\n";
return 0;
}
Compilation message
beads.cpp: In function 'void dfs2(long long int, long long int, long long int, long long int)':
beads.cpp:50:9: warning: unused variable 'old' [-Wunused-variable]
int old =dp[x][0]._1;
^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
5 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
5 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
6 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
5 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
6 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
4992 KB |
Output is correct |
23 |
Correct |
10 ms |
5504 KB |
Output is correct |
24 |
Correct |
11 ms |
5532 KB |
Output is correct |
25 |
Correct |
11 ms |
5504 KB |
Output is correct |
26 |
Correct |
16 ms |
6016 KB |
Output is correct |
27 |
Correct |
17 ms |
5988 KB |
Output is correct |
28 |
Correct |
16 ms |
6012 KB |
Output is correct |
29 |
Correct |
15 ms |
5888 KB |
Output is correct |
30 |
Correct |
17 ms |
6016 KB |
Output is correct |
31 |
Correct |
17 ms |
6400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4992 KB |
Output is correct |
2 |
Correct |
6 ms |
4992 KB |
Output is correct |
3 |
Correct |
6 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
4992 KB |
Output is correct |
5 |
Correct |
6 ms |
4992 KB |
Output is correct |
6 |
Correct |
5 ms |
4992 KB |
Output is correct |
7 |
Correct |
5 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
5120 KB |
Output is correct |
9 |
Correct |
5 ms |
4992 KB |
Output is correct |
10 |
Correct |
5 ms |
4992 KB |
Output is correct |
11 |
Correct |
6 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
4992 KB |
Output is correct |
17 |
Correct |
6 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
4992 KB |
Output is correct |
22 |
Correct |
6 ms |
4992 KB |
Output is correct |
23 |
Correct |
10 ms |
5504 KB |
Output is correct |
24 |
Correct |
11 ms |
5532 KB |
Output is correct |
25 |
Correct |
11 ms |
5504 KB |
Output is correct |
26 |
Correct |
16 ms |
6016 KB |
Output is correct |
27 |
Correct |
17 ms |
5988 KB |
Output is correct |
28 |
Correct |
16 ms |
6012 KB |
Output is correct |
29 |
Correct |
15 ms |
5888 KB |
Output is correct |
30 |
Correct |
17 ms |
6016 KB |
Output is correct |
31 |
Correct |
17 ms |
6400 KB |
Output is correct |
32 |
Correct |
77 ms |
9976 KB |
Output is correct |
33 |
Correct |
71 ms |
9976 KB |
Output is correct |
34 |
Correct |
119 ms |
10076 KB |
Output is correct |
35 |
Correct |
389 ms |
24684 KB |
Output is correct |
36 |
Correct |
368 ms |
24696 KB |
Output is correct |
37 |
Correct |
375 ms |
24824 KB |
Output is correct |
38 |
Correct |
308 ms |
24112 KB |
Output is correct |
39 |
Correct |
307 ms |
23896 KB |
Output is correct |
40 |
Correct |
333 ms |
23844 KB |
Output is correct |
41 |
Correct |
396 ms |
28648 KB |
Output is correct |