树形dp二次扫描与换根板子

基本上只有换跟时不一样
这个题时其他节点到这个节点的距离和乘这点的权值的最值

#include<stdio.h>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll sum[200005],dp[200005],a[200005],dp1[200005],sum1=0;
vector<ll> v[200005];
void dfs(ll x,ll fa){
   
	sum[x]=a[x];
	for(ll i=0;i<v[x].size();i++){
   
		ll y=v[x][i];
		if(y==fa)	continue;
		dfs(y,x);
		sum[x]+=sum[y];
		dp[x]+=sum[y]+dp[y];
	}
}
void dfs1(ll x,ll fa){
   
	if(x!=1)	dp1[x]=dp[fa]-dp[x]-sum[x]+dp1[fa]+sum1-sum[x];
	for(ll i=0;i<v[x].size();i++){
   
		ll y=v[x][i];
		if(y==fa)	continue;
		dfs1(y,x);
	}
}
int main(){
   
	ll n;
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
   
		scanf("%lld",&a[i]);
		sum1+=a[i];
	}
	for(ll i=1;i<n;i++){
   
		ll x,y;
		scanf("%lld%lld",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,-1);
	dfs1(1,-1);
	ll maxx=0;
	for(ll i=1;i<=n;i++)
		maxx=max(maxx,dp[i]+dp1[i]);
	printf("%lld\n",maxx);
	return 0;
}