Solution
经典树上dp。
我们发现一个节点统计 or不统计答案影响下一级，所以dp时需要加上这个状态。
树上dp虽然名义上叫dp，但一般是基于记忆化搜索实现（
第二层状态就统计以其为根节点的子树快乐最大值就好啦！
上面已经分析了状态，如下：
\(f_{i,j}(i\in{0,1)}\)表示选or不选\(j\)时以\(j\)为父节点的子树快乐最大值。
状态转移方程：\(f_{0,j}+=max(f_{0,k},f_{1,k})\) 其中\(k\)为\(j\)的直接儿子。显然若不选\(j\)则可以选\(k\)，取选或不选的max即可。
同理，若选上\(j\),则一定不能选\(k\)，状态转移方程：\(f_{1,j}+=f_{0,k}+a_j\)
此类情况显然需要初始化\(f_{1,j}=a_j\)
对于边界呢？
如果搜到叶子节点，直接令\(f_{0,j}=0,f_{1,j}=a_j\)即可。因为叶子节点如果选则为它本身，如果不选择为0.
此外本题明确是棵树，但是没有给root，需要我们自己记录一下每个点的入度，入度为0的点即为root。显然root是唯一的。
最后答案即为\(max(f_{1,root},f_{0,root})\)
记忆化搜索实现注意一些细节。
Code
/*
树形dp典题
显然一个职员去or不去会影响到下一个职员，所以需要设置两重状态。即职员去or不去。
树形dp通常基于记忆化搜索实现。显然只有职员更新完后上司才能更新（回溯）
如果职员去，那么他的职员就不能去，f[1][i] += f[0][Edge[i][j]+a[i]
如果职员不去，那么他的职员可以去，也可以不去，取max即可
哦对了本题没有告诉你root，需要自己记录一下出度，由于保证一定是一个tree，故只有一个出度为0的点。显然只有一个root。
最后答案取root是否去的max即可
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define N 10001
using namespace std;
int n;
vector <int> Edge[N];
int a[N];
int in[N];
int f[N][N];
int vis[N];
void dfs(int pos)
{
if(!Edge[pos].size()) //边界
{
f[0][pos] = 0;
f[1][pos] = a[pos];
return;
}
for(int i=0;i<Edge[pos].size();i++)
{
dfs(Edge[pos][i]); //先dfs，回溯的时候再更新
f[0][pos] += max(f[0][Edge[pos][i]],f[1][Edge[pos][i]]); //分别更新选or不选
f[1][pos] += f[0][Edge[pos][i]];
}
f[1][pos] += a[pos]; //别漏下选择自己
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
Edge[y].push_back(x); //建图
in[x] ++; //存入度确立root
}
int root;
for(int i=1;i<=n;i++)
{
if(!vis[i] && !in[i])
{
root = i;
dfs(i);
}
}
cout<<max(f[1][root],f[0][root])<<endl; //取max即可
return 0;
}