算法訓練：結點選擇

算法訓練：結點選擇（動态規劃）（2017.3.29） 問題描述

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

輸入格式

第一行包含一個整數 n 。

接下來的一行包含 n 個正整數，第 i 個正整數代表點 i 的權值。

接下來一共 n-1 行，每行描述樹上的一條邊。

輸出格式 輸出一個整數，代表選出的點的權值和的最大值。 樣例輸入 5

1 2 3 4 5

1 2

1 3

2 4

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

#include<iostream> #include<vector> using namespace std; vector<int>node[100001];

  int dp[100001][2];    int visit[100001]; int value[100001]; void Dfs(int tn) {

    int i;

    dp[tn][0]=0; 

    dp[tn][1]=value[tn];

    visit[tn]=1;

    for(i=0;i<node[tn].size();i++)

    {

        int son;

        son=node[tn][i];

        if(visit[son])

            continue;

        Dfs(son);

        dp[tn][1]=dp[tn][1]+dp[son][0];

        dp[tn][0]=dp[tn][0]+max(dp[son][0],dp[son][1]);

    } } int max(int a,int b) {

    if(a>b)

        return a;

    else

        return b;  } int main() {

    int n,x,y,Max;

    int i;

    cin>>n;

    for(i=1;i<n+1;i++)

    {

        cin>>value[i];

        visit[i]=0;

    }

    for(i=1;i<n;i++)

    {

        cin>>x>>y;

        node[x].push_back(y);

        node[y].push_back(x);

    }

    Dfs(1);

    Max=dp[1][0];

    Max=max(Max,dp[1][1]);

    cout<<Max;

    return 0; }