lanqiao oj 131 生命之树

简介: 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 ;
}
目录
打赏
0
0
0
0
24
分享
相关文章
|
9月前
lanqiao OJ 364 跳石头
lanqiao OJ 364 跳石头
71 6
作用域和作用域链及预解析
作用域和作用域链及预解析
53 4
|
9月前
lanqiaoOJ 563 采药
lanqiaoOJ 563 采药
42 6
|
9月前
lanqiao OJ 239 最优包含
lanqiao OJ 239 最优包含
41 2
|
9月前
lanqiao OJ 230 调手表
lanqiao OJ 230 调手表
68 1
c语言回顾-数组(全网最详细,哈哈哈)(上)
c语言回顾-数组(全网最详细,哈哈哈)(上)
104 0
|
9月前
|
AcWing 271. 杨老师的照相排列
AcWing 271. 杨老师的照相排列
58 0
|
9月前
acwing272. 最长公共上升子序列
acwing272. 最长公共上升子序列
50 0
|
9月前
lanqiao OJ 金明的预算方案
lanqiao OJ 金明的预算方案
34 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问