lanqiao oj 131 生命之树

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std ;
typedef long long LL ;
const int N = 1e5 +10 ;
LL w[N] ;
LL n ;
vector<LL> tree[N] ;//利用邻接表存储树
LL res ;
LL dp[N] ;//以i为结尾的子树的最大分数值
 
void dfs(LL u , LL fa ){//利用深搜遍历这一棵子树
  for(int i = 0 ; i < tree[u].size() ; i++ ){//遍历每一个树的子树
    LL son = tree[u][i] ;//取当前这个点作为根节点
    if(son != fa){
      dfs(son,u) ;
      if(dp[son]>0) dp[u] += dp[son] ;
    }
  }
  res = max(res , dp[u]) ;//对每一个子树取最大值
}
int main(){
  cin >> n ; 
  for(int i = 1 ; i <= n ; i ++) cin >> w[i] ,dp[i] = w[i];
  for(int i = 1 ; i < n ; i ++ ){
    int u , v ; cin >> u >> v ;
    tree[u].push_back(v) ; 
    tree[v].push_back(u) ;
  }
  dfs(1,-1) ;// 任意选一个节点开始搜索
  cout << res << endl ;
}