I - Tree with Maximum Cost

题意：选择一个点作为根节点，然后每个顶点到它的花费为距离那个顶点的值。求最大值。
思路：也是树形dp，dp[i]代表考虑以i为根节点，他的子树对他的花费，sum[i]代表i整颗子树的节点个数和，那么dfs两次就行了，第一次dfs预处理出来sum和dp数组，第二次处理出每个点的答案。u节点的答案就是ans[u]=dp[u]+(all-sum[u])+ans[p]-sum[u]-dp[u]=all+ans[p]-2sum[u];
AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n;
const int N=200010;
int a[N];
int sum[N];
int sum2[N];
int ans[N];
int all;
int idx;
int h[N],ne[N*2],e[N*2]; 
void add(int a,int b)
{
   
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa)
{
   
	sum[u]=a[u];
	sum2[u]=0;
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(j==fa)
		continue;
		dfs(j,u);
		sum[u]+=sum[j]; 
		sum2[u]+=sum2[j];
		sum2[u]+=sum[j];
	}
}
void dfs2(int u,int fa)
{
   
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(j==fa)	continue;
		ans[j]=(all-sum[j]*2+ans[u]);
		dfs2(j,u);	
	}
}
signed main()
{
   
	memset(h,-1,sizeof h);
	cin >> n;
	for(int i=1;i<=n;i++)
	cin>>a[i],all+=a[i];
	for(int i=0;i<n-1;i++)
	{
   
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs(1,-1); 
	ans[1]=sum2[1];
	dfs2(1,-1);
	int res=0;
	for(int i=1;i<=n;i++)
	res=max(res,ans[i]);
	cout<<res<<endl;
	return 0;
}