lanqiao OJ 131 生命之树

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
 
using namespace std ;
const int N = 1e6 + 10 ;
typedef long long LL ;
vector<int> e[N] ;//用邻接表存储图 
int w[N] ;
int n ; 
LL res = 0 ;
LL f[N] ;
void dfs(int u , int fa){
  f[u] = w[u]
  for(int i = 0 ; i < e[u].size() ; i ++){
    int j = e[u][i] ;
    if(j != fa){//不回走父结点 
      dfs(j,u) ;
      if(f[j] > 0 ) f[u] += f[j] ;
    }
  }
  //res = max(res,f[u]);
}
int main(){
  cin >> n ;
  for(int i = 1 ; i <= n ;i ++) cin >> w[i] ;
  for(int i = 1 ; i < n ; i ++){
    int a , b ; cin >> a >> b ;
    e[a].push_back(b) ; e[b].push_back(a) ;
  }
  dfs(1,-1) ;//任选一个结点进行dfs 
  
  for(int i = 1 ; i <= n ; i ++) res = max(res,f[i]);
  cout << res << endl ;
}