蓝桥杯算法训练（四）结点选择（树形动态规划）C语言

短命女 2022-03-09 21:14 181阅读 0赞

# 结点选择（树形动态规划）C语言 #

**问题描述**

有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？

**输入格式**

第一行包含一个整数 n 。

接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行，每行描述树上的一条边。

**输出格式**

输出一个整数，代表选出的点的权值和的最大值。

**样例输入**  
5  
1 2 3 4 5  
1 2  
1 3  
2 4  
2 5

**样例输出**  
12

**样例说明**  
选择3、4、5号点，权值和为 3+4+5 = 12 。

**数据规模与约定**

对于20%的数据， n <= 20。

对于50%的数据， n <= 1000。

对于100%的数据， n <= 100000。

权值均为不超过1000的正整数。

--------------------

前面也说了，这道题笔者花了相当长的时间，但其实细究起来，最重要的就三个点：

1.建树  
（但这道题并不是简单的单个头结点，每个结点只有一个父结点的那种普通的树，它实际是个无向图！）

2.递推式  
（这个难度比较小），但是不太好解释 ，讲不清楚请原谅哈~~♪( ^ ∇ ^ \*) ，直接写基本思路:

**深度遍历每一个结点，每个结点都进行一次判断：**  
**如果取这个结点，那么该结点的子结点就不取，如果不取该结点，那么它的子结点有两种情况：可以取，也可以不取！**

于是有状态方程：

dp\[x\]\[0\]表示x结点不选中时最大的权值,dp\[x\]\[1\]表示x结点选中时最大的权值

状态转移方程：dp\[x\]\[1\] = dp\[x\]\[1\] + dp\[u\]\[0\] (u为x的子结点)  
　　　　　　　dp\[x\]\[0\] = dp\[x\]\[0\] + max\{dp\[u\]\[0\],dp\[u\]\[1\]\}(u为x的子结点)  
　　　　　　  
（看不懂就多看几遍，自己纸上画一下，花点时间总是能懂的。）

3。树（无向图）的遍历  
（事实上，树的遍历还是比较容易的，只要注意多叉树与二叉树之间的转换就很容易实现，祥见[上一篇博客的代码][Link 1]（这几个字是链接））

**但是！无向图的遍历就复杂了好多，这也是这篇博客的重点！！！**

因为网上能找到的的代码基本都是千篇一律，但那段代码笔者是真的看不懂~~

但功夫不负有心人，我终于找到了一篇好东西！！

[链式前向星https://blog.csdn.net/lala\_\_lailai/article/details/79249809][https_blog.csdn.net_lala_lailai_article_details_79249809]

以上为链接！

在这（两）位大佬的帮助下！笔者终于搞懂了这段神奇的代码！！

但是很显然这种算法笔者很难学得会呀~~呜呜呜…

哎，讲得乱七八糟的，希望读者大大们能看懂~~

看不懂就动笔一步一步跟着代码走，相信你一定会豁（jing）然（wei）开（tian）朗（ren）的~~

以上！

[Link 1]: https://blog.csdn.net/qq_39913187/article/details/88092126
[https_blog.csdn.net_lala_lailai_article_details_79249809]: https://blog.csdn.net/lala__lailai/article/details/79249809

发表评论取消回复

表情：

评论列表（有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读

相关【蓝桥杯】蓝桥杯入门训练+蓝桥杯基础训练

BEGIN-1 A+B问题资源限制时间限制：1.0s 内存限制：256.0MB 问题描述输入A、B，输出A+B。输入格式输入的第一行包括两个

野性酷女/ 2022年12月03日 01:59/ 0 赞/ 458 阅读

相关算法训练结点选择（树形dp）（点权）

问题描述有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？输入格式第一行

ゝ一纸荒年。/ 2022年09月27日 06:52/ 0 赞/ 174 阅读

相关蓝桥杯结点选择（树形动态规划）

这道题就是一道树的最大独立集问题。先看一下题目要求：问题描述有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被

小咪咪/ 2022年05月31日 06:48/ 0 赞/ 175 阅读

相关蓝桥杯算法训练数列

问题描述　　给定一个正整数k(3≤k≤15),把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列，例如，当k=3时，这个序列是：　　

本是古典何须时尚/ 2022年04月23日 12:50/ 0 赞/ 331 阅读

相关蓝桥杯入门训练（四） A+B求和问题 C语言

A+B求和问题 C语言问题描述输入A、B，输出A+B。输入格式输入的第一行包括两个整数，由空格分隔，分别表示A、B。输出格式输出一行，包括一个

落日映苍穹つ/ 2022年04月22日 20:04/ 0 赞/ 187 阅读

相关蓝桥杯入门训练Fibonacci数列 C语言

Fibonacci数列 C语言问题描述 Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。当n比较大时，Fn也非常大，现在我们

青旅半醒/ 2022年04月12日 13:13/ 0 赞/ 304 阅读

相关蓝桥杯：JAVA结点选择（树形动态规划）

private static int dp[][] = new int[10002][2]; private static int tree[][] = new

野性酷女/ 2022年04月03日 16:48/ 0 赞/ 161 阅读

相关蓝桥杯算法训练（三） K好数（动态规划） C语言

K好数 C语言问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L

蔚落/ 2022年03月20日 17:56/ 0 赞/ 324 阅读

相关蓝桥杯算法训练传纸条（动态规划）

问题描述　　小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线

怼烎@/ 2022年03月16日 15:46/ 0 赞/ 180 阅读

相关蓝桥杯算法训练（四）结点选择（树形动态规划）C语言

结点选择（树形动态规划）C语言问题描述有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权

短命女/ 2022年03月09日 21:14/ 0 赞/ 182 阅读