信息学奥赛一本通T1582-周年纪念晚会(树形DP)

解题思路:

注意事项:

参考代码:

#include <iostream>

#include <vector>

using namespace std;

const int MAXN = 6010;

int dp[MAXN][2];

vector<int> edge[MAXN];

int n;

bool isChild[MAXN];

void dfs(int node)

{

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

    {

        int child = edge[node][i];

        dfs(child);

        dp[node][0] += max(dp[child][0], dp[child][1]);

        dp[node][1] += dp[child][0];

    }

}

int main()

{

    cin >> n;

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

    {

        cin >> dp[i][1];

    }

    int x, y;

    while (true)

    {

        cin >> x >> y;

        if (x == 0 && y == 0)

        {

            break;

        }

        edge[y].push_back(x);

        isChild[x] = true;

    }

    int root = 1;

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

    {

        if (!isChild[i])

        {

            root = i;

            break;

        }

    }

    dfs(root);

    cout << max(dp[root][1], dp[root][0]) << endl;

return 0;

}