hdu 1011 树形dp
HDU 4126 Genghis Khan the Conqueror MST+树形dp
题意： 给定n个点m条边的无向图。 以下m行给出边和边权 以下Q个询问。 Q行每行给出一条边（一定是m条边中的一条） 表示改动边权。 （数据保证改动后的边权比原先的边权大） 问：改动后的最小生成树的权值是多少。 每一个询问互相独立（即每次询问都是对于原图改动） 保证没有重边。 求：全部改动后的最小生成树权值的平均值。 思路： 首先跑一个最小生成树。 求得这个MST的权值 int mst;
日期 2023-06-12 10:48:40
hdu2196 树形DP
题意: 给你一棵树,求出每一个点到其他点的最大距离. 思路: 每个点的最大距离只有两种情况,1是自己忘下面走的最大,二是网上走的最大,取他们的最大便是答案,每个点网下面的最大可以空过dfs直接在回溯的时候求出来,但网上走的
日期 2023-06-12 10:48:40hdu2196 树形DP
题意: 给你一棵树,求出每一个点到其他点的最大距离. 思路: 每个点的最大距离只有两种情况,1是自己忘下面走的最大,二是网上走的最大,取他们的最大便是答案,每个点网下面的最大可以空过dfs直接在回溯的时候求出来,但网上走的
日期 2023-06-12 10:48:40
hdu4126(MST + 树形dp
题意: 这个题目和hdu4756差不多,是给你一个图,然后是q次改变边的权值,权值只增不减,最后问你每次改变之后的最小树的平均值是多少. 思路:(prim+树形dp) 先跑一边最小树(建议用普利姆,别用克鲁斯卡尔,虽然网上
日期 2023-06-12 10:48:40
hdu4126(MST + 树形dp
题意: 这个题目和hdu4756差不多,是给你一个图,然后是q次改变边的权值,权值只增不减,最后问你每次改变之后的最小树的平均值是多少. 思路:(prim+树形dp) 先跑一边最小树(建议用普利姆,别用克鲁斯卡尔,虽然网上
日期 2023-06-12 10:48:40
hdu4756 最小树+树形dp
题意: 给你一个完全图,让你在上面找到一颗最小树,然后问破坏这个最小树的某一条边后用其他边连接(要求最小)成新的树,然后输出破坏每一条边后最小树中最大的那个. 思路: 先跑出一颗最小树,然后枚举树上的每一条边,当这条边被删
日期 2023-06-12 10:48:40hdu4756 最小树+树形dp
题意: 给你一个完全图,让你在上面找到一颗最小树,然后问破坏这个最小树的某一条边后用其他边连接(要求最小)成新的树,然后输出破坏每一条边后最小树中最大的那个. 思路: 先跑出一颗最小树,然后枚举树上的每一条边,当这条边被删
日期 2023-06-12 10:48:40hdu1561 树形dp
题意： 给你n个东西，每个东西有自己的价值，让你从里面最多取出m个物品，问最大的价值，有的物品有限制，就是必须先取出某个物品后才能取出这个物品。 思路： 树形dp，应该是树形的01背包吧，自己dp太渣了，看题解看了好久才懂
日期 2023-06-12 10:48:40hdu1561 树形dp
题意： 给你n个东西，每个东西有自己的价值，让你从里面最多取出m个物品，问最大的价值，有的物品有限制，就是必须先取出某个物品后才能取出这个物品。 思路： 树形dp，应该是树形的01背包吧，自己dp太渣了，看题解看了好久才懂
日期 2023-06-12 10:48:40hdu5293 Tree chain problem 树形dp+线段树
题目：http://acm.hdu.edu.cn/showproblem.php?pid=5293 在一棵树中，给出若干条链和链的权值。求选取不相交的链使得权值和最大。 比赛的时候以为是树链剖分就果断没去想，事实上是没思路。 看了题解，原来是树形dp。话说多校第一场树形dp还真多。。。。 维护d[i],表示以i为根节点的子树的最优答案。 sum[i]表示i的儿子节点（仅仅能是儿子节点
日期 2023-06-12 10:48:40HDU 2196 Computer 树形DP经典题
链接：http://acm.hdu.edu.cn/showproblem.php?pid=2196 题意：每一个电脑都用线连接到了还有一台电脑，连接用的线有一定的长度，最后把全部电脑连成了一棵树，问每台电脑和其它电脑的最远距离是多少。 思路：这是一道树形DP的经典题目。须要两次DFS，第一次DFS找到树上全部的节点在不同子树中的最远距离和次远的距离（在递归中进行动态规划就可以），第二次DFS
日期 2023-06-12 10:48:40HDU 6567 Cotree (树的重心+并查集+树形DP)
Cotree Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1215 Accepted Submission(s): 416 Problem De
日期 2023-06-12 10:48:40HDU 6201 transaction transaction transaction (树形DP)
题意：给定一棵树，每个点有一个点权，每条边也是，找一条路径，问你 T-S-sum，T表示路径的终点的权值，S表示路径始点的权值，sum表示从S到T的边权和。 析：把这一条路径拆开来看，那么就是必然是从 a 先经过一个公共祖先 i，然后再到达b，所以，dp[i][0] 表示 从 i 结点到子树结点中能得到的最大值（到终点），dp[i][1] 表示从子结点到 i 结点能得到的最大值（始点），然后答案
日期 2023-06-12 10:48:40
HDU 3586 Information Disturbing (树形DP+二分)
题意：给出n个士兵，其中1号为指挥官，关系为树状结构，叶子为先锋，现在要在总花费小于等于m的情况切断所有的先锋与指挥官的联系，问最大的限制最小为多少。 析：很明显是一个树形DP，但是限制怎么求呢，就是通过二分，然后变成一个判定性问题，dp[i] 表示切断 以 i 的子树的最少花费不多少，当然是不超过限制的，这里就状态转移方程也是好写的dp[i] += min(dp[v], val)
日期 2023-06-12 10:48:40HDU 5834 Magic boy Bi Luo with his excited tree (树形DP)
题意：给定一棵树，每个点有个权值，每条边有权值，每经过边都会消耗相应的权值，但是点的权值只能获得一次，问你从 i 点出发能获得的最大权值是多少。 析：树形DP，就是太麻烦了，两次dfs，维护一共6个值分别是，从 i 出发的最大值并且返回 i， 从 i 出发的最大值并且不返回，从 i 出发的次大值并且不返回，从 i 出发的最大值的子树结点并且不返回，从 i 向父结点出发的最大值并且不返回，从 i
日期 2023-06-12 10:48:40HDU 1520 Anniversary party (树形DP)
题意：题目给出一棵树，每个节点都有其权值。如果选择了一个节点则不可以选择其父节点，问能取得的最大值。 析：一个简单的树形DP，dp[i][0] 表示结点 i不选，dp[i][1] 表示 结点 i 选，最后选最大值就好。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #i
日期 2023-06-12 10:48:40HDU 2196 Computer (树形DP)
题意：给定一棵树，然后让你找出每个结点离所有结点的最远距离。 析：也就说我们要知道离每个结点的最远距离，对于每个结点，我们知道离它最远的，要么是从父结点过来，要么是从子树中得到，dp[i][0] 表示从 i 子树中得到的 最远距离，dp[i][1] 表示 i 从子树得到的次远距离，dp[i][2] 表示从 父结点得到的最大距离，我们要搜索两次，第一次就是搜索子树，很容易得到最远距离和次远距离，
日期 2023-06-12 10:48:40HDU 4756 Install Air Conditioning (MST+树形DP)
题意：n-1个宿舍，1个供电站，n个位置每两个位置都有边相连，其中有一条边不能连，求n个位置连通的最小花费的最大值。 析：因为要连通，还要权值最小，所以就是MST了，然后就是改变一条边，然后去找出改变哪条能使得总花费最大，dp[i][j] 表示那条边左边的 i 和右边的 j， 最短距离，然后枚举MST里面的每条边，就能知道哪是最大了，注意 供电站和宿舍之间的边不能考虑的。 代码如下： #pra
日期 2023-06-12 10:48:40HDU 4126 Genghis Khan the Conqueror (树形DP+MST)
题意：给一图，n个点，m条边，每条边有个花费，给出q条可疑的边，每条边有新的花费，每条可疑的边出现的概率相同，求不能经过原来可疑边 （可以经过可疑边新的花费构建的边），注意每次只出现一条可疑的边，n个点相互连通的最小花费的期望。 析：要想连通先让他们连通起来，先构造出一个MST，然后再暴力，如果这个边不在这里面，那么花费不变，如果在里面，那我们需要知道是用原来的边最少， 还是再找一条边使他们连通
日期 2023-06-12 10:48:40HDU 4714 Tree2cycle (树形DP)
题意：给定一棵树，断开一条边或者接上一条边都要花费 1，问你花费最少把这棵树就成一个环。 析：树形DP，想一想，要想把一棵树变成一个环，那么就要把一些枝枝叶叶都换掉，对于一个分叉是大于等于2的我们一定要把它从父结点上剪下来是最优的， 因为如果这样剪下来再粘上花费是2（先不管另一端），如果分别剪下来再拼起来，肯定是多花了，因为多了拼起来这一步，知道这，就好做了。先到叶子结点， 然后再回来计算到底要
日期 2023-06-12 10:48:40HDU 4514 湫湫系列故事――设计风景线 (树形DP)
题意：略。 析：首先先判环，如果有环直接输出，用并查集就好，如果没有环，那么就是一棵树，然后最长的就是树的直径，这个题注意少开内存，容易超内存， 还有用C++交用的少一些，我用G++交的卡在32764K，限制是32768K。。 代码如下： #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio>
日期 2023-06-12 10:48:40【HDU - 4340】Capturing a country（树形DP）
BUPT2017 wintertraining(15) #8A 题意 n(<100)个城市组成的树。A攻击i城市需要a[i]代价，B需要b[i]。如果一个城市的邻居被A攻击了，那么A攻击它只要A[i]/2（整除）的代价，B同理。求攻击全部城市的最小代价。 题解 这题很容易想到树形dp。 每个节点为根的子树，有可能是： A从根的上面攻击下来， A从根或下面攻击到根上面， B从根的上面攻击下来
日期 2023-06-12 10:48:40HDU 4313 Matrix 树形dp
题意： 给定n个点的树，m个黑点 以下n-1行给出边和删除这条边的费用 以下m个黑点的点标[0,n-1] 删除一些边使得随意2个黑点都不连通。 问删除的最小花费。 思路： 树形dp 每一个点有2个状态，成为黑点或白点。 若本身这个点就是黑点那么仅仅有黑点一种状态。 否则能够觉得是子树中某个黑点转移上来。 所以dp[i][0]是i点为黑点的状态。 #pragma comment(linke
日期 2023-06-12 10:48:40