P3647 [APIO2014] 连珠线 / 换根 DP
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=2e5+10;
#define pii pair<int,int>
vector<pii>g[N];
int n,f[N],ans;
inline int read(){char c=getchar();int f=1,ans=0;while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();return ans*f;
}
inline int max(int a,int b,int c){return max(max(a,b),c);}
multiset<int,greater<int> >s[N];
inline void tfer(int u,int v,int w,int op){if (op) f[u]+=max(f[v],f[v]+*s[v].begin()+w),s[u].insert(f[v]+w-max(f[v],f[v]+*s[v].begin()+w));else f[u]-=max(f[v],f[v]+*s[v].begin()+w),s[u].erase(s[u].find(f[v]+w-max(f[v],f[v]+*s[v].begin()+w)));
}
void dfs1(int u,int fa){s[u].insert(-1e18);for (auto i:g[u]) if (i.first^fa) dfs1(i.first,u),tfer(u,i.first,i.second,1);
}
void dfs2(int u,int fa){ans=max(ans,f[u]);for (auto i:g[u]) if (i.first^fa){int v=i.first,w=i.second;tfer(u,v,w,0),tfer(v,u,w,1);dfs2(v,u);tfer(v,u,w,0),tfer(u,v,w,1);}
}
main(){n=read();for (int i=1,u,v,w;i<n;i++) u=read(),v=read(),w=read(),g[u].push_back({v,w}),g[v].push_back({u,w}); dfs1(1,0),dfs2(1,0);cout <<ans<<endl;return 0;
}
