#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010, INF=1e15;
int n, pw[N], dp[2][N], ep[2][N];
vector<pair<int, int>> adj[N];
void dfs(int curr, int prev) {
int mx1=-INF, mx2=-INF, mx3=-INF, mx4=-INF, mx5=-INF, sum=0;
vector<pair<int, int>> vec;
for(auto [next, w]:adj[curr]) if(next!=prev) {
pw[next]=w, dfs(next, curr);
sum+=max(dp[0][next], ep[0][next]);
if(dp[0][next]>=ep[0][next]) {
if(mx1<w) mx2=mx1, mx1=w;
else if(mx2<w) mx2=w;
}
else {
if(mx1<dp[0][next]+w-ep[0][next]) mx2=mx1, mx1=dp[0][next]+w-ep[0][next];
else if(mx2<dp[0][next]+w-ep[0][next]) mx2=dp[0][next]+w-ep[0][next];
}
vec.push_back({mx1, mx2});
}
dp[0][curr]=sum, ep[0][curr]=sum+mx1+pw[curr], ep[1][curr]=sum+mx1+pw[curr], dp[1][curr]=max(sum, sum+mx1+mx2);
reverse(adj[curr].begin(), adj[curr].end());
int p=vec.size()-1;
for(auto [next, w]:adj[curr]) if(next!=prev) {
int tmx3=mx3, tmx4=mx4;
if(tmx3<w) tmx4=tmx3, tmx3=w;
else if(tmx4<w) tmx4=w;
int tmp=tmx3+tmx4;
if(p) tmp=max({tmp, tmx3+vec[p-1].first, vec[p-1].first+vec[p-1].second});
dp[1][curr]=max(dp[1][curr], sum-max(dp[0][next], ep[0][next])+dp[1][next]+tmp);
dp[1][curr]=max(dp[1][curr], sum-max(dp[0][next], ep[0][next])+max(dp[1][next], ep[1][next]));
p--;
if(dp[0][next]>=ep[0][next]) {
if(mx3<w) mx4=mx3, mx3=w;
else if(mx4<w) mx4=w;
}
else {
if(mx3<dp[0][next]+w-ep[0][next]) mx4=mx3, mx3=dp[0][next]+w-ep[0][next];
else if(mx4<dp[0][next]+w-ep[0][next]) mx4=dp[0][next]+w-ep[0][next];
}
}
p=vec.size()-1;
for(auto [next, w]:adj[curr]) if(next!=prev) {
ep[1][curr]=max(ep[1][curr], sum-max(dp[0][next], ep[0][next])+dp[1][next]+w+pw[curr]);
ep[1][curr]=max(ep[1][curr], sum-max(dp[0][next], ep[0][next])+ep[1][next]+max(mx5, p?vec[--p].first:-INF)+pw[curr]);
if(dp[0][next]>=ep[0][next]) mx5=max(mx5, w);
else mx5=max(mx5, dp[0][next]+w-ep[0][next]);
}
}
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});
}
dfs(1, 0);
cout<<max(dp[0][1], dp[1][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... |