【题目】

Ural大学有N名职员，编号为1~N。
他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。
每个职员有一个快乐指数，用整数 HiHi 给出，其中 。
现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。
在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

【题解】

这道题的性质在线性dp中有类似的，就是不能取相邻的数，使取出来的数总和最大。这道题的做法也差不多，也是用一个dp数组来进行dp，不过这次是树形dp。就是不让这个人去,就是让这个人去。而因为这道题的树形dp就是从树的最底层，也就是公司的最基础的员工向上状态转移，而状态转移方程则是，（u为父亲，v为左儿子或者右儿子），意思就是如果当前的上司选择不去，那么就能取直系下属选择去和不去的最优值，而如果上司选择去，那么只能选直系下属不去的情况。所以在深度遍历回溯时，所代表的就是当前以作为其子树的最高上司时的最优解。那么到了最后的树的最高层，也就是公司的顶级上司这时(选没有直系上司的人，当)，所求的值，便是这道题的最优解。

时间复杂度：

#include<iostream>
#include<cstring>
#include<sstream>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<list>
#include<set>
#include<map>
#include<algorithm>
#define fi first
#define se second
#define MP make_pair
#define P pair<int,int>
#define PLL pair<ll,ll>
#define lc (p<<1)
#define rc (p<<1|1)
#define MID (tree[p].l+tree[p].r)>>1
#define Sca(x) scanf("%d",&x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x)
#define Scl2(x,y) scanf("%lld%lld",&x,&y)
#define Scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define Pri(x) printf("%d\n",x)
#define Prl(x) printf("%lld\n",x)
#define For(i,x,y) for(int i=x;i<=y;i++)
#define _For(i,x,y) for(int i=x;i>=y;i--)
#define FAST_IO std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define STOP system("pause")
#define ll long long
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;
const double Pi = acos(-1.0);
using namespace std;
template <class T>void tomax(T&a,T b){ a=max(a,b); }  
template <class T>void tomin(T&a,T b){ a=min(a,b); }
const int N= 6000+5;
const int M= 6000+5;
int head[N],num[N],dp[N][2];
int Root;
bool d[N];
int idx=0;
struct E{
    int v;
    int nxt;
}edge[M<<1];
void dfs(int u){
    for(int i=head[u];~i;i=edge[i].nxt){
        int v=edge[i].v;
        dfs(v);
        dp[u][0]+=max(dp[v][1],dp[v][0]);
        dp[u][1]+=dp[v][0];
    }
    dp[u][1]+=num[u];
}
inline void add_edge(int u,int v){
    edge[idx]=E{v,head[u]}; head[u]=idx++;
}
inline void init(int n){
    idx=0;
    memset(dp,0,sizeof(dp));
    memset(head,-1,sizeof(head));
}
int main(){
    int n;
    while(~Sca(n)){
        init(n);
        For(i,1,n) Sca(num[i]);
        while(1){
            int u,v; Sca2(v,u);
            if(u==0&&v==0) break;
            add_edge(u,v);    
            d[v]=1;
        }
        For(i,1,n)
            if(d[i]==0) Root=i;
        dfs(Root);
        printf("%d\n",max(dp[Root][0],dp[Root][1]));
    }
}