年会 （C++代码）

        Dp苦手（ 。

参考代码:

#ifndef LOCAL
    #include <bits/stdc++.h>
#endif
constexpr auto Inf = 0X3F3F3F3F;
typedef long long LL;
using namespace std;

namespace IO {
    inline LL read() {
        LL o = 0, f = 1; char c = getchar();
        while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
        while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
        return o * f;
    }
    inline char recd() {
        char o; while ((o = getchar()) != '(' && o != ')'); return o;
    }
}
using namespace IO;

const int SIZE = 1E5 + 7, Mod = 1E9 + 7;
vector<int> G[SIZE];
LL w[SIZE], Dp[SIZE][2]; int vs[SIZE];

void DFS(int u) {
    Dp[u][1] = w[u];
    for (int e = 0; e < G[u].size(); e++) {
        int v = G[u][e];
        DFS(v);
        Dp[u][0] += max(Dp[v][1], Dp[v][0]);
        Dp[u][1] += Dp[v][0];
    }
}

int main() {
    int N = read();
    for (int pos = 1; pos <= N; pos++) w[pos] = read();
    for (int pos = 1, u, v; pos < N; pos++)
        u = read(), v = read(), G[v].push_back(u), vs[u] = 1;
    for (int pos = 1; pos <= N; pos++)
        if (!vs[pos]) {
            DFS(pos), printf("%lld\n", max(Dp[pos][1], Dp[pos][0]));
            break;
        }
}