#include <bits/stdc++.h>
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
inline int read (void) {
int x = 0, f = 1, ch = getchar();
while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); }
while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }
return x * f;
}
const int maxn = 200005;
int tot_edge, head[maxn], to[maxn<<1], link[maxn<<1], cost[maxn<<1];
inline void add_edge (int x, int y, int c) {
to[++tot_edge] = y;
cost[tot_edge] = c;
link[tot_edge] = head[x];
head[x] = tot_edge;
}
int fa[maxn], len[maxn], f[maxn][2];
std::vector <int> v[maxn], dp[maxn][2], mx[maxn];
void dfs (int x, int Fa=0) {
f[x][1] = -1 << 30;
int mx1 = -1 << 30, mx2 = -1 << 30;
for(int now=head[x]; now; now=link[now]) {
if(to[now] == Fa) continue;
fa[to[now]] = x;
len[to[now]] = cost[now];
v[x].push_back (to[now]);
dfs (to[now], x);
f[x][0] += std::max(f[to[now]][0], f[to[now]][1] + cost[now]);
int v = f[to[now]][0] + cost[now] - std::max(f[to[now]][0], f[to[now]][1] + cost[now]);
if(v > mx1) mx2 = mx1, mx1 = v;
else if(v > mx2) mx2 = v;
}
f[x][1] = f[x][0] + mx1;
for(int now=head[x]; now; now=link[now]) {
if(to[now] == Fa) continue;
dp[x][0].push_back (f[x][0] - std::max(f[to[now]][0], f[to[now]][1] + cost[now]));
if(f[to[now]][0] + cost[now] - std::max(f[to[now]][0], f[to[now]][1] + cost[now]) == mx1)
dp[x][1].push_back (dp[x][0].back() + mx2), mx[x].push_back (mx2);
else
dp[x][1].push_back (dp[x][0].back() + mx1), mx[x].push_back (mx1);
}
}
int ans;
void solve (int x) {
int s = v[x].size();
FOR(i,0,s-1) {
f[x][0] = dp[x][0][i], f[x][1] = dp[x][1][i];
if(fa[x]) {
f[x][0] += std::max(f[fa[x]][0], f[fa[x]][1] + len[x]);
f[x][1] = f[x][0] + std::max(mx[x][i], f[fa[x]][0] + len[x] - std::max(f[fa[x]][0], f[fa[x]][1] + len[x]));
}
ans = std::max(ans, f[v[x][i]][0] + std::max(f[x][0], f[x][1] + len[v[x][i]]));
solve (v[x][i]);
}
}
int main (void) {
int n = read();
FOR(i,2,n) {
int x = read(), y = read(), c = read();
add_edge (x, y, c);
add_edge (y, x, c);
}
dfs (1); solve (1);
printf("%d\n", ans);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19028 KB |
Output is correct |
2 |
Correct |
11 ms |
19108 KB |
Output is correct |
3 |
Correct |
11 ms |
19028 KB |
Output is correct |
4 |
Correct |
10 ms |
19092 KB |
Output is correct |
5 |
Correct |
11 ms |
19156 KB |
Output is correct |
6 |
Correct |
11 ms |
19060 KB |
Output is correct |
7 |
Correct |
11 ms |
19028 KB |
Output is correct |
8 |
Correct |
11 ms |
19028 KB |
Output is correct |
9 |
Correct |
10 ms |
19028 KB |
Output is correct |
10 |
Correct |
10 ms |
19092 KB |
Output is correct |
11 |
Correct |
11 ms |
19072 KB |
Output is correct |
12 |
Correct |
10 ms |
19096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19028 KB |
Output is correct |
2 |
Correct |
11 ms |
19108 KB |
Output is correct |
3 |
Correct |
11 ms |
19028 KB |
Output is correct |
4 |
Correct |
10 ms |
19092 KB |
Output is correct |
5 |
Correct |
11 ms |
19156 KB |
Output is correct |
6 |
Correct |
11 ms |
19060 KB |
Output is correct |
7 |
Correct |
11 ms |
19028 KB |
Output is correct |
8 |
Correct |
11 ms |
19028 KB |
Output is correct |
9 |
Correct |
10 ms |
19028 KB |
Output is correct |
10 |
Correct |
10 ms |
19092 KB |
Output is correct |
11 |
Correct |
11 ms |
19072 KB |
Output is correct |
12 |
Correct |
10 ms |
19096 KB |
Output is correct |
13 |
Correct |
11 ms |
19136 KB |
Output is correct |
14 |
Correct |
10 ms |
19096 KB |
Output is correct |
15 |
Correct |
11 ms |
19064 KB |
Output is correct |
16 |
Correct |
11 ms |
19156 KB |
Output is correct |
17 |
Correct |
10 ms |
19156 KB |
Output is correct |
18 |
Correct |
11 ms |
19072 KB |
Output is correct |
19 |
Correct |
12 ms |
19028 KB |
Output is correct |
20 |
Correct |
10 ms |
19064 KB |
Output is correct |
21 |
Correct |
13 ms |
19076 KB |
Output is correct |
22 |
Correct |
11 ms |
19156 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19028 KB |
Output is correct |
2 |
Correct |
11 ms |
19108 KB |
Output is correct |
3 |
Correct |
11 ms |
19028 KB |
Output is correct |
4 |
Correct |
10 ms |
19092 KB |
Output is correct |
5 |
Correct |
11 ms |
19156 KB |
Output is correct |
6 |
Correct |
11 ms |
19060 KB |
Output is correct |
7 |
Correct |
11 ms |
19028 KB |
Output is correct |
8 |
Correct |
11 ms |
19028 KB |
Output is correct |
9 |
Correct |
10 ms |
19028 KB |
Output is correct |
10 |
Correct |
10 ms |
19092 KB |
Output is correct |
11 |
Correct |
11 ms |
19072 KB |
Output is correct |
12 |
Correct |
10 ms |
19096 KB |
Output is correct |
13 |
Correct |
11 ms |
19136 KB |
Output is correct |
14 |
Correct |
10 ms |
19096 KB |
Output is correct |
15 |
Correct |
11 ms |
19064 KB |
Output is correct |
16 |
Correct |
11 ms |
19156 KB |
Output is correct |
17 |
Correct |
10 ms |
19156 KB |
Output is correct |
18 |
Correct |
11 ms |
19072 KB |
Output is correct |
19 |
Correct |
12 ms |
19028 KB |
Output is correct |
20 |
Correct |
10 ms |
19064 KB |
Output is correct |
21 |
Correct |
13 ms |
19076 KB |
Output is correct |
22 |
Correct |
11 ms |
19156 KB |
Output is correct |
23 |
Correct |
12 ms |
19664 KB |
Output is correct |
24 |
Correct |
12 ms |
19616 KB |
Output is correct |
25 |
Correct |
12 ms |
19668 KB |
Output is correct |
26 |
Correct |
15 ms |
20256 KB |
Output is correct |
27 |
Correct |
18 ms |
20264 KB |
Output is correct |
28 |
Correct |
13 ms |
19924 KB |
Output is correct |
29 |
Correct |
13 ms |
19796 KB |
Output is correct |
30 |
Correct |
13 ms |
19924 KB |
Output is correct |
31 |
Correct |
16 ms |
20904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
19028 KB |
Output is correct |
2 |
Correct |
11 ms |
19108 KB |
Output is correct |
3 |
Correct |
11 ms |
19028 KB |
Output is correct |
4 |
Correct |
10 ms |
19092 KB |
Output is correct |
5 |
Correct |
11 ms |
19156 KB |
Output is correct |
6 |
Correct |
11 ms |
19060 KB |
Output is correct |
7 |
Correct |
11 ms |
19028 KB |
Output is correct |
8 |
Correct |
11 ms |
19028 KB |
Output is correct |
9 |
Correct |
10 ms |
19028 KB |
Output is correct |
10 |
Correct |
10 ms |
19092 KB |
Output is correct |
11 |
Correct |
11 ms |
19072 KB |
Output is correct |
12 |
Correct |
10 ms |
19096 KB |
Output is correct |
13 |
Correct |
11 ms |
19136 KB |
Output is correct |
14 |
Correct |
10 ms |
19096 KB |
Output is correct |
15 |
Correct |
11 ms |
19064 KB |
Output is correct |
16 |
Correct |
11 ms |
19156 KB |
Output is correct |
17 |
Correct |
10 ms |
19156 KB |
Output is correct |
18 |
Correct |
11 ms |
19072 KB |
Output is correct |
19 |
Correct |
12 ms |
19028 KB |
Output is correct |
20 |
Correct |
10 ms |
19064 KB |
Output is correct |
21 |
Correct |
13 ms |
19076 KB |
Output is correct |
22 |
Correct |
11 ms |
19156 KB |
Output is correct |
23 |
Correct |
12 ms |
19664 KB |
Output is correct |
24 |
Correct |
12 ms |
19616 KB |
Output is correct |
25 |
Correct |
12 ms |
19668 KB |
Output is correct |
26 |
Correct |
15 ms |
20256 KB |
Output is correct |
27 |
Correct |
18 ms |
20264 KB |
Output is correct |
28 |
Correct |
13 ms |
19924 KB |
Output is correct |
29 |
Correct |
13 ms |
19796 KB |
Output is correct |
30 |
Correct |
13 ms |
19924 KB |
Output is correct |
31 |
Correct |
16 ms |
20904 KB |
Output is correct |
32 |
Correct |
39 ms |
25252 KB |
Output is correct |
33 |
Correct |
36 ms |
25196 KB |
Output is correct |
34 |
Correct |
40 ms |
25256 KB |
Output is correct |
35 |
Correct |
180 ms |
44100 KB |
Output is correct |
36 |
Correct |
172 ms |
44120 KB |
Output is correct |
37 |
Correct |
193 ms |
44044 KB |
Output is correct |
38 |
Correct |
72 ms |
36300 KB |
Output is correct |
39 |
Correct |
69 ms |
34896 KB |
Output is correct |
40 |
Correct |
74 ms |
36800 KB |
Output is correct |
41 |
Correct |
170 ms |
51924 KB |
Output is correct |