【生命之树】

2024-08-29 22:52
文章标签 生命 之树

本文主要是介绍【生命之树】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

思路

求联通区域中的最大和值

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10, M = N << 1;
const int null = -0x3f3f3f3f;
long long w[N];
int h[N], e[M], ne[M], idx;
void add(int a, int b)  // 添加一条边a->b
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int n;
long long ans = null;
long long dfs(int f, int u)
{long long bsx = 0;  //branches sum maxfor(int k = h[u]; ~k; k = ne[k]){int j = e[k];if(j == f) continue;long long d = dfs(u, j);if(d > 0) bsx += d;}ans = max(ans, bsx+w[u]);return bsx+w[u];
}
int main()
{cin >> n;for(int i = 1; i <= n; i++){cin >> w[i];}memset(h, -1, sizeof h);for(int i = 0; i < n-1; i ++){int a, b;cin >> a >> b;add(a, b); add(b, a);}dfs(0, 1);cout << ans;return 0;
}

注意

题目说节点绝对值不大于10^{6},说明 bsx 和 函数返回值会爆 int,同时由于使用了 max 函数,所以w[ ]  和 ans 也需要开 long long

这篇关于【生命之树】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1119083

相关文章

created生命周期函数获取不到vuex数据解决方法

问题:在created中获取vuex数据,然后去后端请求数据,发现获取的vuex数据不存在。 解决方法:使用watch监听vuex数据,当数据发生变化在去后端请求数据

生命在于运动

程序员和设计师大部分时间都坐在电脑前。有效的锻炼有助于他们更好地工作。 传统的: 当坐在电脑桌前的时候 脚触地。双手在肘部弯曲。打字时手应搁在桌子上。键盘和鼠标应在触手可及的地方。显示屏应在视线水平上,不高不低。光线最好应来自上方。即光线应该从天花板上照下来。每隔20分钟远眺。可降低眼睛长时间盯着近距离物体产生的疲劳。鼠标和手差不多大小。使用全尺寸符合人体工学的键盘。我个人比较喜欢Mi

【舞动生命,不缺营养!】亨廷顿舞蹈症患者必知的维生素补给站

Hey小伙伴们~👋 今天我们来聊聊一个既特别又需要我们温柔以待的话题——亨廷顿舞蹈症(HD)。在这个充满挑战的旅程中,除了医疗团队的精心治疗,合理的饮食与维生素补充也是不可或缺的支持力量哦!🌈 🌿维生素B家族:大脑的守护者 首先,让我们从维生素B家族说起吧!维生素B群,特别是B6、B12和叶酸,对神经系统健康至关重要。🧠 对于亨廷顿舞蹈症患者而言,它们能帮助缓解神经退行性病变带来的不适

借助文本样式为网页赋予生命——WEB开发系列28

文本样式不仅仅是装饰,它对用户体验和网站的可读性有着重要影响。 一、基本文本和字体样式 1. 字体 CSS 中的字体属性定义了文本的外观,包括字体的类型、大小、粗细等。我们来详细了解这些属性: 字体颜色 使用 ​​color​​​ 属性可以设置文本的颜色。例如: p {color: #333; /* 深灰色 */} 字体种类 ​​font-family

Vue(十三) 路由、路由嵌套、query、param传参、propos、replace属性。编程式路由导航,特有的生命周期函数,路由守卫

文章目录 路由1. 基本使用2. 多级(嵌套)路由3. 路由query传参4. 命名路由5. 路由param传参6. propos属性7. replace属性8. 编程式路由导航9. 缓存路由组件10. actived,deactived生命周期函数11. 路由守卫1、全局路由2、独享路由3、组件内路由守卫 12. 路由器工作的两种模式 路由 路由就是一组key-value的

【舞动生命,不缺营养!】亨廷顿舞蹈症患者的维生素秘籍✨

Hey小伙伴们~👋 在这个充满色彩的世界里,每个人都是独一无二的舞者,但对于患有亨廷顿舞蹈症的朋友来说,他们的舞蹈却多了几分挑战与不易。💪 今天,就让我带你一起揭秘,那些能够助力亨廷顿舞蹈症患者“舞”动更精彩生活的维生素宝藏吧!🎁 🌈 维生素B群:能量加油站! 首先登场的是我们的维生素B群小伙伴,它们可是神经系统的好帮手!🧠 对于亨廷顿舞蹈症患者来说,维持神经系统的稳定至关重要。维生

(二)、软硬件全开源智能手表,可全面高精度采集生命体征数据,进行健康检测。(HealthyPi Move)

HealthyPi Move是一款开放式硬件设备,可让您高精度地跟踪所有生命体征。它不仅仅是另一款带有心率监测器的智能手表,它还是手腕上的完整生命体征监测和记录设备,可以测量心电图(ECG)、光电容积脉搏波 (PPG)、SpO₂、血压(基于手指)、EDA/GSR、心率变异性(HRV)、呼吸频率,甚至体温。  01、特性与规格 微控制器:Nordic nRF5340 双核 ARM M3

羊皮卷之五:假如今天是我生命中的最后一天

本文固定链接:http://blog.csdn.net/u013108312/article/details/53579227 假如今天是我生命中的最后一天。   我要如何利用这最后、最宝贵的一天呢?首先,我要把一天的时间珍藏好,不让一分一秒的时间滴漏。我不为昨日的不幸叹息,过去的已够不幸,不要再赔上今日的运道。   时光会倒流吗?太阳会西升东落吗?我可以纠正昨天的错误吗?我能扶平昨日的创伤

基于layui实现简单的万智牌生命计数器页面

对照手机App“旅法师营地”的万智牌生命计数器窗口(如下图所示),使用layui、jQuery等实现简单的万智牌生命计数器页面。   主要实现的功能如下:   1)点击左右两侧的-1、+1、-5、+5区域更新左右两侧生命值;   2)点击左右两侧的八面、二十面、六面、硬币区域生成左右两侧随机数,模拟掷骰子、掷硬币效果。   还搞不懂上图中的调节局数的上下箭头、中间的刷新按钮是如何布局,暂时就

考研——生命轨迹中一段无法抹去的铿锵岁月

不少人说考研是痛苦的,很少有人说考研是快乐的。然而,无论是痛苦还是快乐,经历过的人都会把曾经的苦与乐看成是自己走向成熟的一段经历,一种克服人生困境的能力和一笔无形的宝贵财富。一路走来,学会了承受和容忍,也学会了坚强与坚持。多年以后,可能时光不在,但是记忆犹新。或许某一天,当闲暇追忆往事时,我依然会为选择考研而感觉亢奋与喜悦。因为那是一段为梦想而奋斗的日子,是人生美好的东西,值得珍惜。所以,感