AcWing 287. 积蓄程度 树形dp，换根

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=4e5+10;
int e[N],w[N],h[N],ne[N],idx;
int ans;
int n;
int deg[N];
int d[N];
int dp[N];
void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
}
//子节点更新父节点 
int dfs_d(int u,int fa)
{
	int p=0;
	d[u]=0;
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(j==fa)
			continue;
		p+=min(w[i],dfs_d(j,u));
	}
	//注意需要特判 
	if(deg[u]!=1)
		return d[u]=p;
	else
		return d[h[u]]+w[h[u]];
}
void dfs_u(int u,int fa)
{
	for(int i=h[u];i!=-1;i=ne[i])
	{
		int v=e[i];
		if(v==fa)
			continue;
		//这一部分画图便于理解 
		if(deg[u]==1)
			dp[v]=w[i]+d[v];
		else
			dp[v]=d[v]+min(w[i],dp[u]-min(w[i],d[v])) ;
		ans=max(ans,dp[v]);
		dfs_u(v,u);
	}
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		idx=0;
		ans=0;
		memset(deg,0,sizeof deg);
		memset(h,-1,sizeof h);
		cin>>n;
		for(int i=1;i<n;i++)
		{
			int a,b,c;
			cin>>a>>b>>c;
			add(a,b,c);
			add(b,a,c);
			deg[a]++;
			deg[b]++;
		} 
		dp[1]=dfs_d(1,-1);
		dfs_u(1,-1);
		for(int i=1;i<=n;i++)
			ans=max(ans,dp[i]);
		cout<<ans<<endl;
	}
	return 0;
}