算法1

(记忆化搜索) $O(n)$

dfs(node, true)表示选node的最大值， dfs(node,false)表示不选node的最大值， 为了加快速度用记忆化的方式

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int C = 6005;

int hi[C], h[C], ne[C], e[C], idx;
bool has_parent[C];
int dp[C][2];

void add(int x, int y) {
    ne[idx] = h[x];
    e[idx] = y;
    h[x] = idx++;
}

int dfs(int node, bool select) {
    if (dp[node][select] != -1) return dp[node][select];
    dp[node][1] = hi[node];
    dp[node][0] = 0;
    for (int i = h[node]; i != -1; i = ne[i]) {
        int j = e[i];
        dp[node][1] += dfs(j, false);
        dp[node][0] += max(dfs(j, true), dfs(j, false));
    }
    if (select) return dp[node][1];
    else return dp[node][0];
}
int main() {
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    memset(dp, -1, sizeof dp);
    for (int i = 1; i <= n; i ++) cin >> hi[i];
    int root = 1;
    for (int i = 1; i <= n - 1; i ++) {
        int l, k;
        cin >> l >> k;
        add(k, l);
        has_parent[l] = true;
    }
    for (int i = 1; i <= n; i ++)
        if (has_parent[i] == false) {root = i; break;}
    int ans = max(dfs(root, true), dfs(root, false));
    cout << ans;
    return 0;
}