在树上做动态规化

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

void dfs(vector<vector<int>>& g, int curr, int (*dp)[2], vector<int>& h) {
  dp[curr][1] += h[curr];
  for (const int child : g[curr]) {
    dfs(g, child, dp, h);
    dp[curr][1] += dp[child][0];
    dp[curr][0] += max(dp[child][0], dp[child][1]);
  }
}

int main(void) {
  int n;
  cin >> n;
  vector<vector<int>> g(n + 1);
  vector<int> h(n + 1);
  vector<int> has_parent(n + 1); 

  int dp[n + 1][2];
  memset(dp, 0x0000, sizeof dp);
  for (int i = 1; i <= n; ++i)
    cin >> h[i];

  int child, parent;
  for (int i = 0; i < n - 1; ++i) {
    cin >> child >> parent;
    g[parent].emplace_back(child);
    has_parent[child] = 1;
  }

  int root_id = 1;
  while (has_parent[root_id]) ++root_id;

  dfs(g, root_id, dp, h);
  cout << max(dp[root_id][0], dp[root_id][1]);
  return 0;
}