换根dp裸题,换根其实就是先做一遍dfs后,重新做一遍,第一次用下面的更新上面,第二次用上面的更新下面
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+10; const int inf=0x3f3f3f3f; int h[N],ne[N],e[N],w[N],idx; int in[N]; int d[N],f[N]; int ans; void add(int a,int b,int c){ e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++; } int dfs(int u,int fa){ int i; if(in[u]==1){ d[u]=inf; return d[u]; } d[u]=0; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa) continue; d[u]+=min(w[i],dfs(j,u)); } return d[u]; } void get(int u,int fa){ int i; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(j==fa) continue; if(in[j]==1){ f[j]=d[u]-w[i]; } else{ f[j]=d[j]+min(f[u]-min(d[j],w[i]),w[i]); get(j,u); } } } int main(){ ios::sync_with_stdio(false); int t; cin>>t; while(t--){ int n; cin>>n; int i; ans=0; idx=0; for(i=1;i<=n;i++) h[i]=-1; memset(in,0,sizeof in); for(i=1;i<n;i++){ int a,b,c; cin>>a>>b>>c; add(a,b,c); add(b,a,c); in[a]++; in[b]++; } int root=1; while (root<=n&&in[root] == 1) root ++ ; if (root>n){ cout << w[0] << endl; continue; } dfs(root,-1); f[root]=d[root]; get(root,0); for(i=1;i<=n;i++) ans=max(ans,f[i]); cout<<ans<<endl; } }