题解 | 没有上司的舞会

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;

int n;
int f[N],g[N];
vector<int> G[N];


void dfs(int u){
	for(int v:G[u]){
		dfs(v);
		f[u]=f[u]+g[v];
		g[u]=g[u]+max(f[v],g[v]);
	}
	return;
}

void solve(){
	vector<bool> f_root(n+1,false);
	int x,y;
	for(int i=1;i<=n-1;i++){
		cin>>x>>y;
		G[x].push_back(y);
		f_root[y]=true;
	}
	int root;
	for(int i=1;i<=n;i++){
		if(!f_root[i]){
			root=i;
			break;
		}
	}
	dfs(root);
	cout<<max(f[root],g[root])<<endl;
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>f[i];
	}
	solve();
	
    return 0;
}