实质是一棵二叉树，父亲选了儿子就不能选，但是注意也可以隔代选。由此可知：

$dp[i][0]=∑max(dp[son][0],dp[son][1])$

$dp[i][0]=∑dp[son][0]$

递归自上而下递推dp即可

#include<bits/stdc++.h>
using namespace std;
int n;
int a[6005]={};
int dp[6005][2]={};
//dp[i][j]表示第i个点选或不选的最大价值 
//0代表不选，1代表选 
vector<int> p[6005]={};//存孩子 
int fa[6005]={};//存父亲 
int root=0;//根 
int dfs(int u,int flag){
	if(dp[u][flag]) return dp[u][flag];
	//找到过了就输出 
	int num=0;//总权值 
	if(flag==0){//不选 
		for(int i=0;i<p[u].size();i++){
			int v=p[u][i];
			//下一个点 
			dp[v][0]=dfs(v,0);//记忆化 
			dp[v][1]=dfs(v,1);
			num+=max(dp[v][0],dp[v][1]);
		}
	}else{//选 
		for(int i=0;i<p[u].size();i++){
			int v=p[u][i];
			dp[v][0]=dfs(v,0);
			num+=dp[v][0];
		}
		num+=a[u];
	}
	return dp[u][flag]=num;//记忆化 
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<n;i++){
		int l,k;
		cin>>l>>k;
		p[k].push_back(l);
		//单向，从父亲指向儿子 
		fa[l]=k;
		//存父亲 
	}
	for(int i=1;i<=n;i++) if(!fa[i]){
		root=i;
		//没父亲的就是根 
		break;
	}
	cout<<max(dfs(root,0),dfs(root,1))<<"\n";
	//最后一次比较 
	return 0;
}