记忆化搜索的写法
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int e[N], ne[N], h[N], idx, indeg[N], outdeg[N], happy[N], f[N][2];
void addArc(int x, int y){
e[idx] = y;
ne[idx] = h[x];
h[x] = idx ++;
outdeg[x] ++;
indeg[y] ++;
}
int dp(int root, int chosen){
if(f[root][chosen] != 0x7f7f7f7f)return f[root][chosen];
if(outdeg[root] == 0){
f[root][1] = happy[root];
f[root][0] = 0;
//cout << f[root][chosen] << endl;
return f[root][chosen];
}
f[root][0] = 0;
f[root][1] = happy[root];
for(int i = h[root]; i != -1; i = ne[i]){
int j = e[i];
f[root][0] += max(dp(j, 0), dp(j, 1));
f[root][1] += dp(j, 0);
}
//cout << f[root][chosen] << endl;
return f[root][chosen];
}
int main(){
int n;
cin >> n;
memset(h, -1, sizeof h);
memset(f, 0x7f, sizeof f);
for(int i = 1; i <= n; i ++)cin >> happy[i];
for(int i = 1; i < n; i ++){
int k, l;
cin >> l >> k;
addArc(k, l);
}
int root = 1;
while(indeg[root] > 0)root ++;
int ans = max(dp(root, 0), dp(root, 1));
cout << ans << endl;
return 0;
}