#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define M 2
#define INF 1000000000000000000
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair< ll, ll > pll;
typedef vector< ll > vl;
typedef vector< pll > vll;
ll n;
vll grafo[N];
ll sum[N];
ll best[N][M];
ll dp[N][2];
ll copySum[N];
ll copyBest[N][M];
ll copyDp[N][2];
ll ans[N];
void Add(ll u, ll val)
{
best[u][M-1] = max(best[u][M-1], val);
sort(best[u], best[u] + M, greater< ll >());
return;
}
void Rem(ll u, ll val)
{
for(ll i = 0;i < M;i++)
if(best[u][i] == val)
best[u][i] = -INF;
sort(best[u], best[u] + M, greater< ll >());
return;
}
void Copy(ll a[M], ll b[M])
{
for(ll i = 0;i < M;i++) b[i] = a[i];
return;
}
void DFS(ll u, ll pai, ll wpai)
{
for(ll i = 0;i < M;i++) best[u][i] = -INF;
ll a, b;
for(auto [v, w] : grafo[u])
{
if(v == pai) continue;
DFS(v, u, w);
sum[u] += dp[v][0];
Add(u, (dp[v][1] + w) - dp[v][0]);
}
dp[u][1] = sum[u];
dp[u][0] = dp[u][1];
dp[u][0] = max(dp[u][0], sum[u] + best[u][0] + wpai);
return;
}
void Solv(ll u, ll pai)
{
ans[u] = dp[u][1];
copySum[u] = sum[u];
Copy(best[u], copyBest[u]);
for(ll i = 0;i <= 1;i++) copyDp[u][i] = dp[u][i];
for(auto [v, w] : grafo[u])
{
if(v == pai) continue;
sum[u] -= dp[v][0];
Rem(u, (dp[v][1] + w) - dp[v][0]);
dp[u][1] = sum[u];
dp[u][0] = dp[u][1];
dp[u][0] = max(dp[u][0], sum[u] + best[u][0] + w);
sum[v] += dp[u][0];
Add(v, (dp[u][1] + w) - dp[u][0]);
dp[v][1] = sum[v];
dp[v][0] = dp[v][1];
Solv(v, u);
sum[u] = copySum[u];
Copy(copyBest[u], best[u]);
for(ll i = 0;i <= 1;i++) dp[u][i] = copyDp[u][i];
}
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll u, v, w, i;
cin >> n;
for(i = 1; i < n; i++)
{
cin >> u >> v >> w;
grafo[u].pb({v, w});
grafo[v].pb({u, w});
}
DFS(1, 1, -INF);
Solv(1, 1);
ll resp = 0;
for(i = 1;i <= n;i++) resp = max(resp, ans[i]);
cout << resp << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |