wust-1299-結點選擇(樹形DP)

Problem Description

有一棵 n 個節點的樹，樹上每個節點都有一個正整數權值。如果一個點被選擇了，那麼在樹上和它相鄰的點都不能被選擇。求選出的點的權值和最大是多少？

Input

第一行包含一個整數 n 。 接下來的一行包含 n 個正整數，第 i 個正整數代表點 i 的權值。 接下來一共 n-1 行，每行描述樹上的一條邊。

Output

輸出一個整數，代表選出的點的權值和的最大值。

Sample Input

5
1 2 3 4 5
1 2
1 3
2 4
2 5

Sample Output

12

HINT

樣例說明
選擇3、4、5號點，權值和為 3+4+5 = 12 。

數據規模與約定
對於20%的數據， n <= 20。
對於50%的數據， n <= 1000。
對於100%的數據， n <= 100000。
權值均為不超過1000的正整數。
思路：對於每一個點i，要麼選：val[i]+gson[i]，其中gson[i]表示所有孫子節點的dp值之和；要麼不選：son[i],其中son[i]表示所有兒子節點的dp值之和。題中給出的是無根樹，只需要任選一個節點作為根節點（這裡選1），就可以確定父子關系了。然後用數組模擬棧來建樹，最後再從數組最後一個元素開始往前推（這樣就相當於從樹的最下面一層開始往上推），並且跟新父節點的son值，和祖父節點的gson值。

#include 
using namespace std;

int val[100001],dp[100001],son[100001],gson[100001],first[100001],next[200002],to[200002],que[100001],far[100001];
bool vis[100001];

int main()
{
    int n,i,u,v,ans;

    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++) first[i]=-1,vis[i]=son[i]=gson[i]=dp[i]=0;

        for(i=1;i<=n;i++) scanf("%d",&val[i]);

        for(i=0;i=0;i--)//從樹的最下面一層開始往上推
        {
            dp[que[i]]=val[que[i]]+gson[que[i]]>son[que[i]]?val[que[i]]+gson[que[i]]:son[que[i]];

            ans=ans>dp[que[i]]?ans:dp[que[i]];

            if(far[que[i]]!=-1)
            {
                son[far[que[i]]]+=dp[que[i]];//更新父節點的son值

                if(far[far[que[i]]]!=-1)
                    gson[far[far[que[i]]]]+=dp[que[i]];//更新祖父節點的gson值
            }
        }

        printf("%d\n",ans);
    }
}