10月25日上午曹文《树的相关算法》幻灯片

1、树,1,2,基础知识,2,2,树的定义,树是连通且无环的无向图 等价条件： 连通，且含有n个点、n-1条边 任意两点间恰有一条路径,3,2020/6/22,无根树,满足上述定义、没有其他限制 每个节点的地位是相同的 当做普通的无向图来处理,4,2020/6/22,有根树,在定义的基础上、指定一个节点为“根” 相比无根树，有根树更多地利用树的性质，组织结构更加清晰 树上的问题一般先转化成有根树再解决。,5,2020/6/22,有根树的结构,描述有根树的结构： 若a在b到根的路径上(如a=1,b=3; a=4,b=6)， 则称a是b的祖先、b是a的子孙 特殊地，若a是b的祖先、且a和b相邻(如a=

2、1,b=4; a=5,b=6)，则称a是b的父亲(父节点)，b是a的儿子(子节点) 一个节点及其所有子孙节点组成一棵子树 深度：根据需要定义根的深度为0或1；每走过一条向下的边深度+1,6,2020/6/22,有根树的存储,方法一：除了根没有父亲，所有节点都有唯一的父亲。记录每个节点的父节点即可。缺点是不能从根开始遍历整棵树 应用：并查集 方法二：(同普通的无向图)用邻接表存储。从根开始dfs时得到每个点的父节点，除了父节点外相邻的节点就是子节点。 应用：(很多OI题中)只知道树边的两个端点、不知道父子关系的情况,7,2020/6/22,基本问题,8,2,树的直径,给定一棵树，每条边的长度为1

3、。 定义树的直径是树上最长的路径。注意直径可能有多条。 求直径的长度。,9,2020/6/22,树的直径,暴力O(n2) 枚举路径的一个端点x，dfs求出所有从x开始的路径的长度。,10,2020/6/22,树的直径,经典算法一：简单树形dp 考虑一棵树的直径与其根的关系，它要么经过根，要么完全在根的一个子树里。 如果直径经过根，考虑根将直径分成的两个部分，它们是子树中从根向下的最长的两条路径。 对于直径不经过根的情况递归求解即可。 令fi为从i向下的最长路径长度，dfs过程中统计即可。,11,2020/6/22,树的直径,#include using namespace std; const

4、 int MAXN = 100007; vector EMAXN; int n, ans; int f(int x, int fa) int ret = 1, m1 = 0, m2 = 0; for (int i = 0; i Ex.size(); +i) if (Exi != fa) int r = f(Exi, x); if (ret r + 1) ret = r + 1; if (m1 r) m2 = m1, m1 = r; else if (m2 n; for (int i = 1; i u v; Eu.push_back(v); Ev.push_back(u); f(1, -1);

5、printf(%dn, ans); return 0; ,12,2020/6/22,树的直径,经典算法二： 随便选一个点x，求出距离x最远的一个点y，然后再求出距离y最远的一个点z，yz一定是一条直径。 两遍dfs即可。 证明：关键是证明y一定是某一条直径的一个端点。 用反证法。(?) 类似地也可以证明所有直径都相交 (?),13,2020/6/22,树的中心,对于一棵树，定义r(x)为离x最远的点到x的距离；定义树的中心为满足r(x)最小的点x。 给定一棵树，求它的中心。 所有直径都经过中心。可以用反证法证明。 (?) 中心是任意一条直径的中点。对于直径上有偶数个点的情况存在两个中心。 (?

6、),14,2020/6/22,树的重心,对于一棵树，定义w(x)为将x作为根时、x最大的子树的大小。定义树的重心为满足w(x)最小的点x。 给定一棵树，求它的重心。 暴力O(n2) 枚举每一个x、O(n)求出x所有子树的size 如何优化？,15,2020/6/22,树的重心,首先任意指定一个根。不妨设为节点1。 接下来需要考虑：在指定1为根的情况下如何计算w(x)？ 容易看出x的子树分为两种：x下面的子树 ，以及x上面包含1的部分 包含1的部分可以用n-size(x)来获得 dfs一遍算出所有子树大小即可,16,2020/6/22,树的重心,结论：若x为树的重心，则w(x)n/2 同样用反证

7、法可证。 (?) 当w(x)=n/2时恰有相邻的两个重心，其他情况下重心唯一。 画张图就能看出来。,17,2020/6/22,最近公共祖先,给定一棵有根树，回答若干询问，每次询问两个点a,b的最近公共祖先(LCA)。 不难想到的暴力做法：将ab中较深的向根移到同一深度；然后一起一步一步向根移动，直到两者重合。 优化：用倍增加速这个过程。,18,2020/6/22,最近公共祖先,预处理：记upxi(i=0.logn)为从x向根移动2i步到达的位置(如upx0就是x的父亲)。如果移动到了根以上的位置不妨令为0。 有递推式 uprooti=0; upx0=fax; upxi=upupxi-1i-1;

8、 可以在O(nlogn)时间内预处理。,19,2020/6/22,最近公共祖先,求a,b两点的LCA： 首先将a,b提到同一深度：不妨设a当前比b深，从大到小枚举步长2i，若b不比upai深则更新a。这里i=0.logn，复杂度O(logn) 若此时a=b则返回结果(b) 从大到小枚举步长2i，若upai!=upbi则更新a,b。这里i=0.logn，因此复杂度O(logn) 最后答案即为当前a/b的父节点，即upa0,20,2020/6/22,最近公共祖先,const int logn = 18; int LCA(int a, int b) if (depa = 0; -i) if (dep

9、upai = 0; -i) if (upai != upbi) a = upai, b = upbi; return upa0; ,21,2020/6/22,简单的树上统计,给定一棵树，有边权，每次询问两个点的距离。 n, q 100000 任意指定一个根，求出每个点i到根的路径的边权和sumi。 对于询问(x,y)，求出LCA(x,y)=a，则答案为sumx+sumy-2*suma 单次询问复杂度O(logn),22,2020/6/22,简单的树上统计,给定一棵树，有边权，每次询问两点之间的最大值。 n, q 100000 类比RMQ。令MAXxi为从x向上2i个数的最大值，用类似up的方式

10、预处理。 询问时一边求LCA一边求答案即可。,23,2020/6/22,树同构,给出两棵节点数相同的有根树，问它们是否同构。 基本思想是树哈希：设计一种对于树的哈希函数，并用哈希值相等作为判定树同构的依据。 下面给出一个较为合理的哈希函数作为参考： hashx=(ap xor H1 mod q)p xor H2 mod q)xor Hk mod q)b mod q 其中H1.Hk是对x的所有子树的hash值从小到大排序的结果。排序能够避免子树的顺序不同造成hash的差异。,24,2020/6/22,题目选讲,25,2,BOOSTER,给定一棵有根树，有边权。 初始时只有根和叶子是关键点。 你可以花费1个代价把一个节点变成关键点。 要求花费最小的代价，使得对于所有从叶子到根的路径中，任意相邻两个关键点的距离不超过给定的k。 n105 从叶子向上贪心,26,2020/6/22,GALLERY,给定一棵二叉树，每条边有通过时间ti，每个点有wi件物品。每取一件物品需要花费5个单位时间。要求从根出发，花费总时间不超过k、且最后回到根，获得的物品数量最大。 N100, ti20, wi20, k600 较简单的树上背包,27,2020/6/22,PARTY,给定一棵树，求最大点权独立集。 N100 树形dp，dpx0/1表示子树x、取不取x,28,2