P8625.生命之树

求最大的子树之和

维护包含当前节点的最大子树之和就好了

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6+10;
ll w[N];
vector<int>g[N];
ll f[N];
ll res;

ll dfs(int u,int father){
	
	
	f[u] = w[u];
	
	for(auto &t:g[u]){
		if(t==father)continue;
		
		ll tem = dfs(t,u);
		f[u]+=max(0ll,tem);
		
	}
	
	res = max(res,f[u]);
	//cout<<u<<" "<<f[u]<<"\n";
	return f[u];
	
	
}

int main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i];
	
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	dfs(1,-1);
	cout<<res;
	
}