动态规划

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#define N 6001
using namespace std;
vector<int> g[N];
int dp[N][2], root, flag[N];
void (int x)
{
    for (int i = 0; i < g[x].size();i++)
    {
    	int son=g[x][i];
        dfs(son);
        dp[x][1] = max(max(dp[x][1], dp[x][1] + dp[son][0]), dp[son][0]);
        dp[x][0] = max(max(dp[x][0], dp[x][0] + dp[son][1]), max(dp[son][1], dp[son][0]));
    }
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n;i++)
    {
        cin >> dp[i][1];
    }
    for (int i = 1; i <= n;i++)
    {
        int a, b;
        cin>>a>>b;
        g[b].push_back(a);
        flag[a] = 1;
    }
    for (int i = 1; i <= n;i++)
    {
        if(!flag[i])
        {
            root = i;
            break;
        }
    }
    dfs(root);
    cout << max(dp[root][0], dp[root][1]) << endl;
}