树归之没有上司的舞会

题目

可参照洛谷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;

}