#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 2e5 + 5;
const ll infll = (ll)1e18 + 7;
int n;
vpii adj[N];
int wpar[N];
void dfs(int u, int p){
Fora(&edge, adj[u]){
int v, w; tie(v, w) = edge;
if (v == p){
continue;
}
wpar[v] = w;
dfs(v, u);
}
}
ll dp[N][2];
void dfs_dp(int u, int p){
ll sum = 0, mx = -infll;
Fora(&edge, adj[u]){
int v, w; tie(v, w) = edge;
if (v == p){
continue;
}
dfs_dp(v, u);
sum += dp[v][0];
mx = max(mx, dp[v][1] - dp[v][0]);
}
dp[u][0] = max(sum, sum + mx + wpar[u]);
dp[u][1] = sum + wpar[u];
}
ll ans = -infll;
void dfs_reroot(int u, int p){
ans = max(ans, dp[u][0]);
vector <ll> prefmx(isz(adj[u])), suffmx(isz(adj[u]));
For(i, 0, isz(adj[u])){
int v, w; tie(v, w) = adj[u][i];
prefmx[i] = max(i > 0 ? prefmx[i - 1] : -infll, dp[v][1] - dp[v][0]);
}
FordE(i, isz(adj[u]) - 1, 0){
int v, w; tie(v, w) = adj[u][i];
suffmx[i] = max(i < isz(adj[u]) - 1 ? suffmx[i + 1] : -infll, dp[v][1] - dp[v][0]);
}
int owparu = wpar[u]; ll odpu0 = dp[u][0], odpu1 = dp[u][1], osumu = dp[u][1] - wpar[u];
For(i, 0, isz(adj[u])){
int v, w; tie(v, w) = adj[u][i];
if (v == p){
continue;
}
int owparv = wpar[v]; ll odpv0 = dp[v][0], odpv1 = dp[v][1], osumv = dp[v][1] - wpar[v];
ll mx = -infll;
Fora(&edge, adj[v]){
int tv, tw; tie(tv, tw) = edge;
if (tv == u){
continue;
}
mx = max(mx, dp[tv][1] - dp[tv][0]);
}
wpar[u] = w;
dp[u][0] = max(osumu - dp[v][0], osumu - dp[v][0] + max(i > 0 ? prefmx[i - 1] : -infll, i < isz(adj[u]) - 1 ? suffmx[i + 1] : -infll) + wpar[u]);
dp[u][1] = osumu - dp[v][0] + wpar[u];
wpar[v] = -1e9;
dp[v][0] = max(osumv + dp[u][0], osumv + dp[u][0] + max(mx, dp[u][1] - dp[u][0]) + wpar[v]);
dp[v][1] = osumv + dp[u][0] + wpar[v];
dfs_reroot(v, u);
wpar[v] = owparv; dp[v][0] = odpv0; dp[v][1] = odpv1;
}
wpar[u] = owparu; dp[u][0] = odpu0; dp[u][1] = odpu1;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n;
For(i, 1, n){
int u, v, w; cin >> u >> v >> w;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
wpar[1] = -1e9;
dfs(1, 0);
dfs_dp(1, 0);
dfs_reroot(1, 0);
cout << ans << endl;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5032 KB |
Output is correct |
11 |
Correct |
4 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5032 KB |
Output is correct |
11 |
Correct |
4 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
5032 KB |
Output is correct |
14 |
Correct |
3 ms |
5036 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
4 ms |
5112 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
5012 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5032 KB |
Output is correct |
11 |
Correct |
4 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
5032 KB |
Output is correct |
14 |
Correct |
3 ms |
5036 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
4 ms |
5112 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
5012 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Correct |
7 ms |
5300 KB |
Output is correct |
24 |
Correct |
6 ms |
5392 KB |
Output is correct |
25 |
Correct |
5 ms |
5332 KB |
Output is correct |
26 |
Correct |
8 ms |
5724 KB |
Output is correct |
27 |
Correct |
9 ms |
5716 KB |
Output is correct |
28 |
Correct |
7 ms |
5844 KB |
Output is correct |
29 |
Correct |
8 ms |
5876 KB |
Output is correct |
30 |
Correct |
8 ms |
5808 KB |
Output is correct |
31 |
Correct |
9 ms |
6832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5076 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Correct |
3 ms |
5032 KB |
Output is correct |
11 |
Correct |
4 ms |
4948 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
3 ms |
5032 KB |
Output is correct |
14 |
Correct |
3 ms |
5036 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
4948 KB |
Output is correct |
18 |
Correct |
4 ms |
5112 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
5012 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
4948 KB |
Output is correct |
23 |
Correct |
7 ms |
5300 KB |
Output is correct |
24 |
Correct |
6 ms |
5392 KB |
Output is correct |
25 |
Correct |
5 ms |
5332 KB |
Output is correct |
26 |
Correct |
8 ms |
5724 KB |
Output is correct |
27 |
Correct |
9 ms |
5716 KB |
Output is correct |
28 |
Correct |
7 ms |
5844 KB |
Output is correct |
29 |
Correct |
8 ms |
5876 KB |
Output is correct |
30 |
Correct |
8 ms |
5808 KB |
Output is correct |
31 |
Correct |
9 ms |
6832 KB |
Output is correct |
32 |
Correct |
32 ms |
8636 KB |
Output is correct |
33 |
Correct |
39 ms |
8624 KB |
Output is correct |
34 |
Correct |
39 ms |
8644 KB |
Output is correct |
35 |
Correct |
209 ms |
19840 KB |
Output is correct |
36 |
Correct |
261 ms |
20040 KB |
Output is correct |
37 |
Correct |
231 ms |
19832 KB |
Output is correct |
38 |
Correct |
154 ms |
23088 KB |
Output is correct |
39 |
Correct |
143 ms |
23512 KB |
Output is correct |
40 |
Correct |
162 ms |
23004 KB |
Output is correct |
41 |
Correct |
245 ms |
32892 KB |
Output is correct |