#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010, INF=1e12;
int n, pw[N], dp[N], ep[N];
vector<pair<int, int>> adj[N];
void dfs(int curr, int prev) {
int sum=0;
int mx1=-INF, mx2=-INF, mx3=-INF, mx4=-INF, mx5=-INF, mx6=-INF;
for(auto [next, w]:adj[curr]) if(next!=prev) {
pw[next]=w, dfs(next, curr);
sum+=max(dp[next], ep[next]);
if(dp[next]>=ep[next]) {
if(mx1<w) mx3=mx2, mx2=mx1, mx1=w;
else if(mx2<w) mx3=mx2, mx2=w;
else if(mx3<w) mx3=w;
}
else {
if(mx4<dp[next]+w-ep[next]) mx6=mx5, mx5=mx4, mx4=dp[next]+w-ep[next];
else if(mx5<dp[next]+w-ep[next]) mx6=mx5, mx5=dp[next]+w-ep[next];
else if(mx6<dp[next]+w-ep[next]) mx6=dp[next]+w-ep[next];
}
}
dp[curr]=max({sum, sum+mx1+mx2, sum+mx1+mx4, sum+mx4+mx5});
ep[curr]=max({sum+mx1, sum+mx4, sum+mx1+mx2+mx3, sum+mx1+mx2+mx4, sum+mx1+mx4+mx5, sum+mx4+mx5+mx6})+pw[curr];
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int i=1; i<n; i++) {
int u, v, w; cin>>u>>v>>w;
adj[u].push_back({v, w}), adj[v].push_back({u, w});
}
fill(dp+1, dp+n+1, -INF), fill(ep+1, ep+n+1, -INF);
dfs(1, 0);
cout<<dp[1];
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... |