评测记录：https://www.luogu.com.cn/record/119482090

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

const int N = 10005;
int f[N][2]; 
int r[N];
int din[N];
bool used[N];
vector<int>v[N];
vector<int>v2[N];
int ff[N];
int fa[N];
int maxf;

void init(int n){
	for(int i = 1;i <= n;++ i){
		fa[i] = i;
	}
} 

int find(int w){
	if(fa[w] == w) return w;
	return fa[w] = find(fa[w]);
}

void merge(int a,int b){
	int x = find(a),y = find(b);
	if(x == y) return;
	fa[a] = b;
}

int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;++ i){
		scanf("%d",&r[i]);
	} 
	init(n);
	for(int i = 0;i < n - 1;++ i){
		int x,y;
		scanf("%d %d",&x,&y);
		v[x].push_back(y);
		v2[y].push_back(x);
		merge(x,y);
		din[y] ++;
	}
	queue<int>q;
	for(int i = 1;i <= n;++ i){
		if(din[i] == 0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int x = q.front();
		q.pop();
		
		for(int y : v2[x]){
			if(f[y][0] > 0) f[x][1] += f[y][0];
			if(f[y][1] > 0) f[x][0] += f[y][1];
		}
		f[x][0] += r[x];
		
		if(used[x]) continue;
		used[x] = true;
		for(int k : v[x]){
			din[k] --;
			if(din[k] == 0){
				q.push(k);
			}
		}
	}
	for(int i = 1;i <= n;++ i) ff[i] = -100000;
	for(int i = 1;i <= n;++ i){
		int c = max(f[i][0],f[i][1]);
		int p = find(i);
		ff[p] = max(ff[p],c);
	}
	for(int i = 1;i <= n;++ i) maxf = max(maxf,ff[i] + maxf);
	printf("%d",maxf);
	return 0;
}