夜摘钻石灯

news/2024/10/31 5:34:57/

HCY同学又获金牌了!
大家都在庆祝!叶老师决定给HCY发点奖金以祝贺。不过能得到多少奖金,就要看HCY同学的表现了。
叶老师用n-1条线,把n盏钻石灯连起来,每盏灯在夜幕下都闪烁着一个正整数,这个数就是叶老师要给HCY的奖金,不过由于数字太大,最后给的奖金当然不是人民币,而是卢布,还是分。
当HCY选中一盏灯后,跟这盏灯直接连接的灯就会灭掉,他不能选择,他只能选择那些还是亮着的灯。
当然一直在答疑群里答疑的HCY,当然会选到最高的金额,所有他选中灯的数字和就是他的奖金。

输入
第一行包含一个整数 n ,n<=100000。
接下来的一行包含 n 个正整数,第 i 个灯上写的钱数(灯的编号为1~n)。
接下来一共 n-1 行,每行描述n-1条线连着哪些灯,每行2个整数表示2头的灯的编号。
输出
输出一个整数,代表HCY能获得的最大奖金数。
样例输入:
5
1 2 3 4 5
1 2
1 3
2 4
2 5
样例输出:
12

解答:

这个问题是一个典型的树形动态规划问题,问题的本质是在树形结构中找出一个子集,使得这个子集中所有节点的和最大,并且任意两个节点都不相邻。

我们可以通过深度优先搜索(DFS)的方式,从底向上地计算每个节点的最大值。对于每个节点,我们有两种选择:选择该节点或者不选择该节点。如果我们选择了这个节点,那么我们不能选择它的任何子节点。如果我们没有选择这个节点,那么我们可以选择它的所有子节点。

对于每个节点,我们需要维护两个值:f[i][0]表示不选择节点i时的最大值,f[i][1]表示选择节点i时的最大值。这两个值可以通过以下方式计算:

  • f[i][0] = ∑max(f[j][0], f[j][1])(对于所有j,j是i的子节点)
  • f[i][1] = ∑f[j][0] + a[i](对于所有j,j是i的子节点)

这样,我们可以使用深度优先搜索的方式,从叶节点开始向上计算,最后的结果就是max(f[root][0], f[root][1])

下面是C语言实现的代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define MAXN 100010
#define ll long longtypedef struct Edge {int to;struct Edge* next;
} Edge;Edge* G[MAXN];
ll a[MAXN];
ll f[MAXN][2];
int n;void add_edge(int u, int v) {Edge* edge = (Edge*)malloc(sizeof(Edge));edge->to = v;edge->next = G[u];G[u] = edge;
}void dfs(int u, int fa) {for (Edge* e = G[u]; e; e = e->next) {int v = e->to;if (v == fa) continue;dfs(v, u);f[u][0] += f[v][1] > f[v][0] ? f[v][1] : f[v][0];f[u][1] += f[v][0];}f[u][1] += a[u];
}int main() {scanf("%d", &n);for (int i = 1; i <= n; ++i) {scanf("%lld", &a[i]);}for (int i = 1; i < n; ++i) {int u, v;scanf("%d %d", &u, &v);add_edge(u, v);add_edge(v, u);}dfs(1, 0);printf("%lld\n", f[1][0] > f[1][1] ? f[1][0] : f[1][1]);return 0;
}

这段代码首先读入节点数目和每个节点的值,然后读入每条边的信息并构建图。然后从根节点开始进行深度优先搜索,最后输出根节点的最大值。


http://www.ppmy.cn/news/122200.html

相关文章

柯尼卡美能达打印机c226使用说明_柯尼卡美能达/震旦复印机等各类型号复印机装扫描(SMB扫描)...

柯尼卡美能达/柯美复印机C364e/C454e/C554e/C465e/C307/C367/C360等各类型号复印机装扫描(SMB扫描)

柯尼卡美能达306i提示更换感光鼓定影单元 清零方法

打印量9W9&#xff0c;显示屏提示更换硒鼓或提示更换显影组件和感光鼓组件&#xff0c; 硒鼓和显影组件和感光鼓组件的清零方法。 首先进入机器维修模式方法为&#xff1b;“设置”&#xff0c;左侧的“机器维修”&#xff0c;“计数器”&#xff0c;显示“小键盘”&#xff0…

柯尼卡美能达打印机无法使用ID打印

故障如图&#xff1a; 选择输入方式为【ID&打印】出错&#xff0c;因为认证没有开启。 解决办法&#xff1a; 打印机属性-配置-设备选项-认证&#xff08;改为ON&#xff09;

柯尼卡美能达Konica Minolta bizhub C226 默认管理员密码

亲测 有效 遇到设备&#xff0c;用户说没有改过密码&#xff0c;最后知道是 1234567812345678 柯尼卡美能达Konica Minolta bizhub C226 默认管理员密码 1234567812345678 就是1到8输入两次 网上有查询到6个0或者8个0&#xff0c;或者123456和12345678还有6个1

Win10安装驱动后,无法连接打印机柯尼卡美能达 bizhub 363

Win10系统&#xff0c;在驱动天空安装驱动后&#xff0c;无法连接打印机柯尼卡美能达 bizhub 363 一开始我在控制面板的“设备与打印机”中添加打印机&#xff0c;报错弹框显示&#xff1a;输入码无效。搜索发现以下解决方案&#xff0c;依旧无效 最后&#xff0c;我在设置中的…

柯尼卡美能达Konica Minolta bizhub C7122 打印机驱动

柯尼卡美能达Konica Minolta bizhub C7122 打印机驱动是官方提供的一款一体机&#xff08;打印/扫描&#xff09;驱动&#xff0c;本站收集提供高速下载&#xff0c;用于解决一体机与电脑连接不了&#xff0c;无法正常使用的问题&#xff0c;本动适用于&#xff1a;Windows XP …

柯尼卡美能达c353改语言,柯尼卡美能达bizhub c353c253c203维修手册中文部分2.pdf

柯尼卡美能达bizhub c353c253c203维修手册中文部分2.pdf 6.其它现场维修2007年9月版本1.0166bizhubC353/C253/C203“7.断开3个连接头[1]&#xff0c;然后拆下垂直传送单元[2]。8.拆下3个螺钉[1]&#xff0c;然后拆下金属板[2]。注•两端的螺钉均配有一个垫片。拆下螺钉时请小心…

柯尼卡美能达打印机c226使用说明_产品百科: A4幅面创新代表 柯尼卡美能达bizhub C3300i...

【IT168产品百科】柯尼卡美能达bizhub C3300i A4 彩色复合机&#xff0c;是一款面向企业用户推出的A4幅面彩色产品。该机作为柯尼卡美能达最新创新成果&#xff0c;集多功能、高性能、智慧应用及人性化设计于一身&#xff0c;为企业用户提供了全新的文印解决方案。 柯尼卡美能达…