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 ;
}
目录
相关文章
|
2月前
lanqiao OJ 1505 剪邮票
lanqiao OJ 1505 剪邮票
27 0
|
2月前
lanqiao OJ 182 小朋友崇拜圈
lanqiao OJ 182 小朋友崇拜圈
29 2
|
2月前
lanqiao OJ 131 生命之树
lanqiao OJ 131 生命之树
32 0
|
2月前
lanqiao oj 17136 星球(状态压缩dp)
lanqiao oj 17136 星球(状态压缩dp)
12 0
|
2月前
lanqiao oj 1135 蓝桥幼儿园(并查集)
lanqiao oj 1135 蓝桥幼儿园(并查集)
27 0
|
2月前
lanqiao OJ 2097 青蛙过河
lanqiao OJ 2097 青蛙过河
11 0
|
2月前
lanqiao OJ 110 合根植物
lanqiao OJ 110 合根植物
10 0
|
5月前
【蓝桥杯】[递归]母牛的故事
蓝桥杯——[递归]母牛的故事
65 1
【蓝桥杯】[递归]母牛的故事
|
测试技术 C++ Perl
蓝桥 第八大奇迹 (线段树)
蓝桥 第八大奇迹 (线段树)
过河卒-蓝桥杯-动态规划
过河卒-蓝桥杯-动态规划
131 0