记录编号	568966	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.082 s
提交时间	2022-02-11 16:32:17	内存使用	7.35 MiB

#include <iostream>
#include <algorithm>
#include <cstring>
#define OPEN(x) freopen(#x".in", "r", stdin); freopen(#x".out", "w", stdout)

using namespace std;

const int N = 2e5+10;
int n;
int H[N];
int f[N][2];
int e[N], ne[N], h[N], idx;
bool vis[N];

inline int read(){
	char ch = getchar();
	int res = 0;
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch))
		res = (res + (res << 2) << 1) + (ch ^ 48),
		ch = getchar();
	return res;
}

inline void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } 

void dfs(int u) {
    vis[u] = 1;
    f[u][1] = H[u];
    for(register int i = h[u]; i!=-1; i = ne[i]) {
        int j = e[i];
        if(vis[j]) continue;
        dfs(j);
        f[u][0] += max(f[j][0], f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main() {
    OPEN(profitz);
    //OPEN(test);
    memset(h, -1, sizeof h);
    n = read();
    for(register unsigned int i = 1; i<=n; ++i) H[i] = read();
    for(register unsigned int i = 1; i<n; ++i) {
        int a, b;
        a = read();
        b = read();
        add(b, a), add(a, b);
    }
    dfs(1);
    cout << max(f[1][0], f[1][1]) << '\n';
    return 0;
}