算法：HDU 4679 Terrorist’s destroy（树形dp | 多校8）

题意 给一棵n个节点的树,节点编号为1-n,根节点为1.每条边有权值,砍掉一条边要花费cost(w) 要砍掉一些边, 使得每个叶子节点无法走到根节点. 要求砍掉花费总和不能超过m的情况下,让每条 边花费上限尽量低 思路 二分可以砍的边的权值上限,然后树形dp f[i]: 表示让i子树所有的叶 子节点无法到达i点的最小花费 f[i] = sum { min(w(i,v), f[v]) | v是i的儿子节点 } 而这题有一个 上限权值,即权值大于上限的就不能去砍. 所以上面的转移要改一下 if (w

题目大意 给你一个n个点m条边的无向无环图,在尽量少的节点上放灯,使得所有边都被照亮. 每盏灯将照亮以它为一个端点的所有边. 在灯的总数最小的前提下,被两盏灯同时被照亮的边数应该 尽量大. 思路 这是LRJ<训练指南>上的例题. 这题教会了我一个很有用的技巧:有 两个所求的值要优化,比如让a尽量小,b也尽量小 那么可以转化为让 M*a+b尽量小,其中M应该是 一个比"a的最大值和b的最小值之差"还要大的数 最终的答案为ans/M, ans%M 回到这题,要 求放的灯总数最小

题意 给一颗n个结点的树,节点编号为1~n,问删除一个节点之后,让剩下的分支中节点数量最多的尽 量少. 可能有多种方案,按编号顺序输出. 思路 简单的树形dp. 其实连dp都不能算吧...就是直接 计数统计 先dfs计算每个节点子树的节点个数tot[i]. 再次dfs更新答案: f[i] = max( n-tot[i], max{tot[v] | v是i的儿子} ); 两个dfs可以合并在一个dfs里完成, 复杂度O(n) 代码 /**==============================

题意 有n个洞穴编号为1-n,洞穴间有通道,形成了一个n-1条边的树, 洞穴的入口即根节点是1. 每个洞穴有x只bugs,并有价值y的金子,全部消灭完一个洞穴的虫子,就可以获得这个洞穴的y个金子. 现 在要派m个战士去找金子,从入口进入.每次只有消灭完当前洞穴的所有虫子,才可以选择进入下一个洞穴. 一个战士可以消灭20只虫子,如果要杀死x只虫子,那么要x/20向上取整即(x+19)/20个战士. 如果要 获得某个洞穴的金子,必须留下足够杀死所有虫子的战士数量, 即(x+19)/20个战士,然后这

题意 给一棵n个结点的树,结点编号为0~n-1,顶点是0 每条边都有一个权值. Alice和Bob初始位 置在顶点,要往下一直走到叶子结点. 第一次是由Bob选择走向哪个子结点,第二次轮到Alice,依次轮流 下去... 每走过一条边就会获得相应的权值,Bob希望所走的路径总权值越大越好,而Alice希望越小越好 每次他们都会选择最优解. 最终总权值要在范围[L,R]之内. 问最终Bob希望的最大权值是多少? 思路 f(u, 0)表示第u点由Bob选时的最大值 f(u, 1)表示第u点由Alic

题意 给一棵边有权值的二叉树,节点编号为1-n,1是根节点.求砍掉一些边,只保留q条边,这q条边 构成的子树 的根节点要求是1,问这颗子树的最大权值是多少? 思路 非常经典的一道树形dp题 ,根据我目前做过的题来看,有多道都是由这题衍生出来的. f(i, j) 表示子树i,保留j个节点(注意是 节点)的最大权值.每条边的权值,把它看作是连接的两个节点中的儿子节点的权值. 那么,就可以对所 有i的子树做分组背包,即每个子树可以选择1,2,...j-1条边分配给它. 状态转移为: f(i, j) =

题意 某收费有线电视网计划转播一场重要的足球比赛.他们的转播网和用户终端构成一棵树状结 构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的内部节点. 从 转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的,一场转播的总费用等于传输信号 的费用总和. 现在每个用户都准备了一笔费用想观看这场精彩的足球比赛,有线电视网有权决定给哪 些用户提供信号而不给哪些用户提供信号. 写一个程序找出一个方案使得有线电视网在不亏本的情况 下使观看转播的用户尽可能多. 思路 树形

题意 给一棵n个节点的树, 节点编号1~n, 每个节点有权值val[i],经过这个节点就可以获取这个价值( 不能重复获得) 每一条边有一个花费值w(i,j), 表示走完i和j点的边要花费w(i,j) 现在要从k点出发, 总花费值为m,问总花费不超过m的情况下并且最终要回到出发点,最多可以获取多少价值? 思路 简单树形dp. f(i,j)表示子树i, 用花费j最多可以获得的价值 对与i的每个儿子,可以选择分配花费 2*w, 2*w+1, 2*w+2,...j给它,可以看作是一组物品 对所有儿子做分

题意 n个城市节点构成的一棵树,节点i到节点j的电量损耗为 I*I*R*(i到j的路径所含边数),现 在要在某个结点上修建一个供电站,使得这个结点到所有其它节点的总损耗量最小. 思路 典型的树形dp 可以先用一次dfs求出每一点的子树结点个数num[u],以及每一点到它子树所有结点的总 距离f[u][0]; 然后再用一次dfs,推出每个结点到除去它子树部分的结点总距离f[u][1]. f[v][1] = (f[u][0]-f[v][0]-num[v]) + f[u][1] + n - num[v