题意：

给你一棵树，树上的每一个结点都会有一个权值，你可以选取任意多的结点，但是倘若你获取了某个结点\(a_i\)，那么他的所有直接儿子就都不会被选取，现在问你最大能够获得的权值。

分析：

树形\(dp\)的入门题目

首先有一个显然的一点，对于每一个结点都会有选和不选两种方案。我们不妨设\(dp[x][0/1]\)。其中\(dp[x][0]\)为以结点\(x\)为根的子树且不选取当前结点\(x\)的权值最大值，\(dp[x][1]\)为以结点\(x\)为根的子树且选取当前结点\(x\)的权值最大值。

那么根据题目的意思，倘若没有选取了\(x\)结点，那么所有显然所有的儿子结点都可以去选取，而每个儿子都会有取和不取两种状态，因此有转移方程\(dp[x][0]+=\sum\max(dp[son[x]][0],dp[son[x]][1])\)

而倘若选取了\(x\)结点，那么显然儿子的所有结点都不能选，故有状态转移方程\(dp[x][1]+=\sum(dp[son][0])\)

最后我们只需要获取一下根结点\(root\)的记录，因为树存在着递归的性质，因此我们只需要通过\(dfs\)从叶子向根进行更新即可，最后的答案为\(\max(dp[root][1],dp[root][0])\)

代码：

#include 
    
     #define maxn 6005using namespace std;struct Node{    int to,next;}q[maxn];int head[maxn],cnt=0,val[maxn],dp[maxn][2],inde[maxn];void add_edge(int from,int to){    q[cnt].to=to;    q[cnt].next=head[from];    head[from]=cnt++;}void init(){    memset(head,-1,sizeof(head));    cnt=0;}void dfs(int x){    dp[x][0]=0,dp[x][1]=val[x];    for(int i=head[x];i!=-1;i=q[i].next){        int to=q[i].to;        dfs(to);        dp[x][0]+=max(dp[to][0],dp[to][1]);        dp[x][1]+=dp[to][0];    }}int main(){    int n;    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%d",&val[i]);    }    int from,to;    init();    while(scanf("%d%d",&to,&from)){        if(to==0&&from==0) break;        add_edge(from,to);        inde[to]++;    }    int root=0;    for(int i=1;i<=n;i++){        if(inde[i]==0){            root=i;            break;        }    }    dfs(root);    printf("%d\n",max(dp[root][1],dp[root][0]));    return 0;}