树上问题专题6-换根dp

前置知识

讲解059链式前向星建图

讲解078、讲解079-树型dp，一定要掌握再看本节课

讲解118 -专题1:树上倍增和LCA-上，本节课需要递归函数改成迭代函数的技巧

树上问题专题讲述顺序

• 专题1:树上倍增和LCA-上，讲解118
• 专题2:树上倍增和LCA-下，讲解119
• 专题3:树的重心，讲解120
• 专题4:树的直径，讲解121
• 专题5:树上差分，讲解122
• 专题6:换根dp，讲解123，本节

树上问题专题6-换根dp

换根dp入门题 先解决如下题目，然后对换根dp做整体说明

题目1

最大深度和 给定一棵n个点的树，找到一个节点，使得以这个结点为根时，到达所有节点的深度之和最大如果有多个节点满足要求，返回节点编号最小的测试链接 :https://www.luogu.com.cn/problem/P3478

换根dp

树上的某些问题，需要知道以不同的节点做根的情况下，答案是多少

换根dp的思考重点

如果已经得到父节点做根的答案，怎么加工得到子节点做根的答案，就是所谓的换根 为了达成换根这个目标，可能需要设置若干额外的信息来帮助计算

换根dp的过程

1，先以节点1为头进行树的遍历，收集信息，dfs1过程 2，得到1节点做根的答案，然后从1节点开始再进行树的遍历，求解每个节点做根的答案，dfs2过程 核心在于换根时，答案如何转移

题目2

染色的最大收益 给定一棵n个点的树，初始时所有节点全是白点 第一次操作，你可以选择任意点染黑 以后每次操作，必须选择已经染黑的点的相邻点继续染黑，一直到所有的点都被染完 每次都获得，当前被染色点的白色连通块大小，作为收益 返回可获得的最大收益和 测试链接 : https://www.luogu.com.cn/problem/CF1187E

题目3

翻转道路数量最少的首都 给定一棵n个点的树，但是给定的每条边都是有向的 需要选择某个城市为首都，要求首都一定可以去往任何一个城市 这样一来，可能需要翻转一些边的方向才能做到，现在想翻转道路的数量尽量少 打印最少翻转几条道路就可以拥有首都 如果有若干点做首都时，翻转道路的数量都是最少的，那么打印这些点 测试链接 : https://www.luogu.com.cn/problem/CF219D

题目4

选择节点做根使流量和最大 给定一棵n个点的树，边的边权代表流量限制 从边上流过的流量，不能超过流量限制 现在想知道以某个节点做根时，流到所有叶节点的流量，最大是多少 测试链接 : http://poj.org/problem?id=3585

题目5

每个节点距离k以内的权值和 给定一棵n个点的树，每个点有点权 到达每个节点的距离不超过k的节点就有若干个 把这些节点权值加起来，就是该点不超过距离k的点权和 打印每个节点不超过距离k的点权和 注意k并不大 测试链接 : https://www.luogu.com.cn/problem/P3047

题目6

哪些点可以改造成重心 给定一棵n个点的树，你可以随便删掉一条边，然后随便加上一条边 通过这种方式可以让很多点变成重心 打印所有能变成重心的点 测试链接 : https://www.luogu.com.cn/problem/CF708C 测试链接 : https://codeforces.com/problemset/problem/708/C

讲解120 - 树的重心，一定要先掌握，然后再看本题的解析

题目7

聚会后送每个人回家最短用时 给定一棵n个点的树，边权代表走过边需要花费的时间 给定k个人分别在树上的哪些节点 这k个人选择了一个聚会点，所有的人都去往聚会点进行聚会 聚会结束后，所有人都会上一辆车，车会把每个人送回家 送完最后一个乘客，车不需要回到聚会点 如果聚会点在i，请问从聚会地点出发直到送最后一个人回家，最短用时多少 i = 1 ~ n，打印所有的答案 测试链接 : https://www.luogu.com.cn/problem/P6419

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com