lanqiao OJ 131 生命之树

简介: lanqiao OJ 131 生命之树

用户登录

f[i]表示以i为根的子树的最大权值之和

状态转移:如果子节点及其子树权值和大于0,则加入父节点u的权值,即f[u] += f[son]。

#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 ;
}
目录
相关文章
|
2月前
lanqiao OJ 1505 剪邮票
lanqiao OJ 1505 剪邮票
30 0
|
2月前
lanqiao OJ 182 小朋友崇拜圈
lanqiao OJ 182 小朋友崇拜圈
32 2
|
2月前
lanqiao oj 131 生命之树
lanqiao oj 131 生命之树
32 0
|
2月前
lanqiao oj 1135 蓝桥幼儿园(并查集)
lanqiao oj 1135 蓝桥幼儿园(并查集)
33 0
|
2月前
lanqiao oj 1121 蓝桥公园(floyd)
lanqiao oj 1121 蓝桥公园(floyd)
44 0
|
2月前
lanqiao OJ 2097 青蛙过河
lanqiao OJ 2097 青蛙过河
15 0
|
6月前
【洛谷 P1781】宇宙总统 题解(高精度+结构体排序)
在宇宙总统竞选中,需计算得到最高票者。程序接收$n$($1\leq n\leq 20$)个候选人及其票数,使用自定义比较器`cmp`对结构体数组`vote`按票数长度排序。样例输入5人,票数分别为98765、12365、87954、1022356、985678,输出显示编号为4的候选人(票数1022356)获胜。代码中,结构体`S`包含候选人ID和票数字符串,通过`sort`函数及`cmp`函数按票数长度降序排列,输出首位即为胜者。
40 0
《蓝桥杯每日一题》递推·AcWing 3777. 砖块
《蓝桥杯每日一题》递推·AcWing 3777. 砖块
80 0
|
人工智能 BI
《蓝桥杯每日一题》并查集·AcWing1249. 亲戚
《蓝桥杯每日一题》并查集·AcWing1249. 亲戚
58 0
|
算法 测试技术
蓝桥杯2022年第十三届决赛真题-卡牌——二分法
蓝桥杯2022年第十三届决赛真题-卡牌——二分法
129 0