树形DP

#include <bits/stdc++.h>
using namespace std;
#define MAXN 6006
typedef long long ll;

int r[MAXN];
int n;

//采用链式前向星的方式存储树
struct edge
{
    int u, v, next;

} e[4 * MAXN];

int head[MAXN];
int js_edge = 0;
void add_edge(int u, int v)
{
    js_edge++;
    e[js_edge].u = u;
    e[js_edge].v = v;
    e[js_edge].next = head[u];
    head[u] = js_edge;
}

ll dp[MAXN][2];
bool vis[MAXN] = {false};

void dfs(ll u)
{
    vis[u] = true;
    dp[u][1] = r[u];
    for (int i = head[u]; i != 0; i = e[i].next)
    {
        //被搜索过的就不再搜索
        if (vis[e[i].v])
            continue;

        dfs(e[i].v);
        dp[u][0] += max(dp[e[i].v][0], dp[e[i].v][1]);
        dp[u][1] += dp[e[i].v][0];
    }
}

bool is_root[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    memset(is_root, 1, sizeof(bool) * MAXN);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> r[i];

    int l, k;
    for (int i = n + 2; i <= 2 * n; ++i)
    {
        cin >> l >> k;
        is_root[l] = false;
        add_edge(k, l);
    }

    for (int i = 1; i <= n; ++i)
    {
        //找到根节点
        if (is_root[i])
        {
            dfs(i);
            cout << max(dp[i][0], dp[i][1]) << endl;
            return 0;
        }
    }
}