#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;
template <typename __Tp> void read(__Tp &x) {
int f = 0; x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
if (f) x = -x;
}
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &...y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ...y) { write(x), write(y...); }
const int maxn = 2e5 + 10;
int n, a[maxn];
struct Edge {
int v, w, nxt;
} e[maxn << 1];
int h[maxn], cnt_e;
void add(int x, int y, int z) { e[++cnt_e] = {y, z, h[x]}, h[x] = cnt_e; }
pll mg(pll u, pll v, int w) {
return {u.fir + max(v.fir, v.sec + w),
max(u.sec + max(v.fir, v.sec + w), u.fir + v.fir + w)};
}
pll f[maxn], upf[maxn];
void dfs(int u, int pre) {
f[u] = {0, -1e18};
for (int j = h[u]; j; j = e[j].nxt) {
int v = e[j].v, w = e[j].w;
if (v == pre) continue;
a[v] = w, dfs(v, u), f[u] = mg(f[u], f[v], w);
}
}
pll pr[maxn], sf[maxn];
void dfs2(int u, int pre) {
vector <pll> son;
for (int j = h[u]; j; j = e[j].nxt) {
int v = e[j].v, w = e[j].w;
if (v == pre) continue;
son.push_back({v, w});
}
int len = son.size();
pr[0] = sf[len + 1] = {0, -1e18};
for (int i = 1; i <= len; ++i) pr[i] = mg(pr[i - 1], f[son[i - 1].fir], son[i - 1].sec);
for (int i = len; i >= 1; --i) sf[i] = mg(sf[i + 1], f[son[i - 1].fir], son[i - 1].sec);
for (int i = 1; i <= len; ++i) {
int v = son[i - 1].fir;
upf[v] = {pr[i - 1].fir + sf[i + 1].fir,
max(pr[i - 1].sec + sf[i + 1].fir, pr[i - 1].fir + sf[i + 1].sec)};
upf[v] = mg(upf[v], upf[u], a[u]);
}
f[u] = mg(pr[len], upf[u], a[u]);
for (pll p : son) dfs2(p.fir, u);
}
int main() {
read(n);
for (int i = 1; i < n; ++i) {
int u, v, w; read(u, v, w);
add(u, v, w), add(v, u, w);
}
dfs(1, 0), a[1] = -1e9, upf[1] = {0, -1e18}, dfs2(1, 0);
ll ans = -1e18;
for (int i = 1; i <= n; ++i) ans = max(ans, f[i].fir);
write(ans, '\n');
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
308 KB |
Output is correct |
11 |
Correct |
0 ms |
304 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
308 KB |
Output is correct |
11 |
Correct |
0 ms |
304 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
308 KB |
Output is correct |
21 |
Correct |
1 ms |
304 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
308 KB |
Output is correct |
11 |
Correct |
0 ms |
304 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
308 KB |
Output is correct |
21 |
Correct |
1 ms |
304 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
724 KB |
Output is correct |
24 |
Correct |
1 ms |
736 KB |
Output is correct |
25 |
Correct |
1 ms |
704 KB |
Output is correct |
26 |
Correct |
3 ms |
1124 KB |
Output is correct |
27 |
Correct |
3 ms |
1084 KB |
Output is correct |
28 |
Correct |
2 ms |
1616 KB |
Output is correct |
29 |
Correct |
2 ms |
1344 KB |
Output is correct |
30 |
Correct |
2 ms |
1364 KB |
Output is correct |
31 |
Correct |
3 ms |
2020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
304 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
308 KB |
Output is correct |
11 |
Correct |
0 ms |
304 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
308 KB |
Output is correct |
21 |
Correct |
1 ms |
304 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
724 KB |
Output is correct |
24 |
Correct |
1 ms |
736 KB |
Output is correct |
25 |
Correct |
1 ms |
704 KB |
Output is correct |
26 |
Correct |
3 ms |
1124 KB |
Output is correct |
27 |
Correct |
3 ms |
1084 KB |
Output is correct |
28 |
Correct |
2 ms |
1616 KB |
Output is correct |
29 |
Correct |
2 ms |
1344 KB |
Output is correct |
30 |
Correct |
2 ms |
1364 KB |
Output is correct |
31 |
Correct |
3 ms |
2020 KB |
Output is correct |
32 |
Correct |
14 ms |
4180 KB |
Output is correct |
33 |
Correct |
13 ms |
4228 KB |
Output is correct |
34 |
Correct |
13 ms |
4136 KB |
Output is correct |
35 |
Correct |
77 ms |
16244 KB |
Output is correct |
36 |
Correct |
82 ms |
16336 KB |
Output is correct |
37 |
Correct |
76 ms |
16352 KB |
Output is correct |
38 |
Correct |
60 ms |
24964 KB |
Output is correct |
39 |
Correct |
51 ms |
23132 KB |
Output is correct |
40 |
Correct |
54 ms |
21700 KB |
Output is correct |
41 |
Correct |
84 ms |
28668 KB |
Output is correct |