记录编号	380294	评测结果	AAAAAAAAAA
题目名称	火车站饭店	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.442 s
提交时间	2017-03-08 20:26:16	内存使用	2.31 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
using namespace std;
#define MAXN 100002
vector<int> G[MAXN];
int f[MAXN][2];
bool vis[MAXN];
void dfs(int u){
  vis[u] = true;
  for(int i = 0; i < G[u].size(); i++){
    int to = G[u][i];
    if(!vis[to]){
      dfs(to);
      f[u][0] += f[to][1];
      f[u][1] += max(f[to][1], f[to][0]);  
    }
  }
}
int main(){
  freopen("profitz.in", "r", stdin);
  freopen("profitz.out", "w", stdout);
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i++)
    scanf("%d", &f[i][0]);
  for(int i = 1; i < n; i++){
    int u, v; scanf("%d %d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
  }
  dfs(1);
  printf("%d\n", max(f[1][0], f[1][1]));
  return 0;
}