题目
可参照洛谷p1352
Ural 大学有 N 个职员，编号为 1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。
输入格式
第一行一个整数 N。(1<=N<=6000)
接下来 N 行，第 i+1 行表示 i 号职员的快乐指数(R_i)，接下来 N-1 行，每行输入一对整数 L,K。表示 K 是 L 的直接上司。最后一行输入 0,0。
输出格式
输出最大的快乐指数。
样例
样例输入
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
样例输出
5
思路
这道题是一道很明显的树归题目，我们可以定义f[u][0/1]数组，f[u][1]代表u节点参加会议的最有解，f[u][0]代表u
节点不参加的最优借，设其字节点为v，那么我们就有
f[u][1]=max(f[u][1],f[v][0]+a[u]);//当前节点参加
ans+=max(f[v][1],f[v][0]);//当前节点不参加，叠加字节点情况（ans用来存储当前节点不参加的情况下，即f[u][0]）
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=6000+10;
int f[maxn][2],a[maxn],x,y,head[maxn],len,n,cnt;
struct edge{
int to,next;
}e[maxn*2];
void Add(int x,int y){
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
void dfs(int u,int fa){
f[u][1]=a[u];
int ans=0;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
f[u][1]=max(f[u][1],f[v][0]+a[u]);
ans+=max(f[v][1],f[v][0]);
}
f[u][0]=ans;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
Add(x,y);Add(y,x);
}
scanf("%d%d",&x,&y);
dfs(1,0);
cout<<max(f[1][1],f[1][0])<<endl;
return 0;
}