题意：找一个点作为源点，问能往周围流的最多的水流。树形dp，dp数组代表以i为根的能流的所有水流，转移很简单，看代码，然后我们要处理一下从父节点流下来的值。如图。 之前wa了三十分钟，是因为转移的时候忘记考虑了父节点子树给他的贡献，从上面留下来的水流包括父节点父节点流下来的水流+子树的水流，然后别忘记特判一下当两个端点的时候，两端都可以流。
#include<bits/stdc++.h> using namespace std; const int N=200010; typedef long long ll; ll dp[N]; ll up[N]; ll ans[N]; int h[N],e[N*2],ne[N*2],idx,w[N*2]; int d[N]; void add(int a,int b,int c) { w[idx]=c,e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int fa) { for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue; //cout<<j<<endl; dfs(j,u); if(d[j]==1) dp[u]+=w[i]; else dp[u]+=min(1ll*w[i],dp[j]); } } void dfs_2(int u,int fa) { for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==fa) continue; if(d[j]==1) { if(d[u]==1) up[j]=w[i]; else up[j]=min(w[i]*1ll,up[u]); } else { if(d[u]==1) up[j]=w[i]; else up[j]=min(w[i]*1ll,up[u]+dp[u]-min(dp[j],w[i]*1ll)); } dfs_2(j,u); } } int main() { int t; cin>>t; while(t--) { int n; cin>>n; for(int i=0;i<=n;i++) h[i]=-1,d[i]=0,dp[i]=0,up[i]=0; idx=0; for(int i=0;i<n-1;i++) { int a,b,c; cin>>a>>b>>c; add(a,b,c); add(b,a,c); d[a]++; d[b]++; } //cout<<d[1]<<' '<<d[2]<<endl; dfs(1,-1); ans[1]=dp[1]; dfs_2(1,-1); ll maxv=ans[1]; //cout<<maxv<<endl; for(int i=2;i<=n;i++) ans[i]=dp[i]+up[i],maxv=max(maxv,ans[i]); printf("%lld\n",maxv); } }