HDU1520 Anniversary party 樹形DP

題目連結：HDU1520

題目大意：給你n個點，每個點擁有相應的權值，要求選一部分點使得他們權值和最大，要求父親節點和孩子節點不能同時被選中。

第一次見到樹形DP

注釋寫的很詳細

AC代碼

/*
2017年7月31日11:39:59
HDU1520 
AC代碼 
*/
#include<stdio.h>
const int maxn=+;
//int a[maxn]; 
struct Tree{
    int father;//father 
    int child;//child 
    int brother;//brother 
    int absent,present;//缺席，出席 
    //求兩種狀态 權值更大的一種 
    int calc(){
        return absent > present ? absent : present;
    } 
    //初始化 present 的權值輸入的時候會初始化 
    void init(){
        father = child = brother = absent = ;
    }
}tree[maxn];

void dfs(int root){
    /*
    取目前節點的孩子節點
    如果沒有孩子，則會退出這一層 
    */
    int child=tree[root].child;
    while(child){
        //一直搜到最底層-葉子節點； 
        dfs(child);
        /*
        當父親節點去的時候，孩子節點一定不能去。      
        */ 
        tree[root].present+=tree[child].absent;
        /*
        父節點不去，加上孩子節點 去和不去 兩種狀态的最大值 
        */ 
        tree[root].absent+=tree[child].calc();   
         /*
        搜這個節點的兄弟節點 
        也就是其父親節點下的所有孩子節點 
        */
        child=tree[child].brother;

    }
}
int main(){
    int n,l,k;
    while(~scanf("%d",&n)){
        /*
        這裡wa了好幾次，仔細讀題，題目中給的點是從1-7 
        是以存資料的時候也要從1-7開始存，一開始 我寫的是0-n-1
        一直wa低級錯誤！！！！ 
        */
        for(int i=;i<=n;i++){
            //對每個節點的present權值初始化 
            scanf("%d",&tree[i].present);
            //對該點的其他值進行初始化 
            tree[i].init();
         }  
         /*
         把l節點的父親置為k,再把l節點的兄弟節點置為k節點的孩子節點。
         更新k節點的孩子節點，如果k節點還有孩子，
         那麼下個孩子的兄弟節點就是l 節點
         應該說清楚了吧…… 
         */
         while(scanf("%d%d",&l,&k),l+k){
            tree[l].father=k;
            tree[l].brother=tree[k].child;
            tree[k].child=l;
         }
         for(int i=;i<=n;i++){
            //隻有根節點的父親為 0 
             //尋找根節點 
            if(!tree[i].father){
                dfs(i);
                printf("%d\n",tree[i].calc());
                break;
             }
         }
    }

    return ;
}