【笔记】树上问题

来自\(\texttt{SharpnessV}\)的省选复习计划中的树上问题


树上问题是\(\rm OI\)中必考的难点。


P5018 [NOIP2018 普及组] 对称二叉树

判断带点权有根二叉树是否同构。

因为有根且是二叉树,这极大简化了判断同构的过程。

我们定义函数 bool check(int x,int y) 判断以 \(x/y\) 为根的子树是否同构。

显然两颗树同构,他们的子树也要同构,我们递归下去即可,这样我们就得到了 \(\rm O(N^2)\) 的算法。

只有在两颗子树大小相同的时候才可能同构,子树大小不相同直接剪枝即可。每个点被check时子树大小必定翻倍,所以时间复杂度是 \(\rm O(N\log N)\)。

Code


P2195 HXY造公园

支持加边和查询联通块直径。

根据直径的最长性质,我们加边的时候一定是将两棵子树的直径中点连起来。

所以我们并查集维护直径长度即可。

Code


P1099 [NOIP2007 提高组] 树网的核

求树的直径上的\(\le s\)的一段的偏心距的最小值。

我们可以将直径上的点删除,得到一个森林,然后对每棵计算最大深度。

那么一段的最大偏心距一定是这一段到直径两段的距离,和所有森林的深度的最大值。

有人可能会问森林中有的子树没有接在这一段上啊,但是根据树的直径的性质,这些子树的最大深度一定不大于这一段到直径两段的距离。因为如果大于,则树的直径可以更长。

树的直径的求法有两种。

第一种是两遍\(\rm DFS\),第一遍任取一个点找出距离最远的点\(A\),第二遍找出距离\(A\)最远的点\(B\),\(A-B\)就是直径。不难用反正法证明不存在更长的路径。

第二种方式是任取一个节点为根,然后计算每个节点向下的最大深度,然后枚举\(\rm LCA\)合并答案。

两种方法各有优劣,第一种不能处理负边权,第二种不能求出具体路径。

Code


P3629 [APIO2010]巡逻

\(\rm k=1\)时,不难发现直接求出树的直径即可。

\(\rm k=2\)时,可以看出是两个 \(k=1\) 的叠加。

如果构成一个环,那么除了新加的边,其他的边都要走一遍。

那么两个环的重叠部分需要走两遍。所以在求出树的直径后,将直径上的边权改为\(-1\),再求一次直径就是第二次需要优化的路径。

Code


P3938 斐波那契

思维题。

肉眼可见祖先节点编号小于子孙节点。

首先每天新增的节点数构成斐波那契数列,我们可以求出 \(a\) 是哪一天加入的。

而每一天新增节点编号是连续的一段,新增节点的父节点编号也是连续的一段,所以新增节点与父节点的编号差就是斐波那契数列的项。

Code


P4281 [AHOI2008]紧急集合 / 聚会

求三个点在树上的重心。

显然重心在任意两点的路径上。

我们先求出\(x-y\)的路径,再求出\(z\)到路径上的最小值。根据\(\rm LCA\)的高低讨论一下即可。

Code


P5658 [CSP-S2019] 括号树

定义状态\(f[i]\)表示\(1-i\)路径构成的串,以\(i\)结尾的合法括号串个数

显然当\(i\)为'('时\(f[i]=0\)

当\(i\)为')'并且没有相应的左括号与其匹配时,\(f[i]=0\)

设与')'匹配的左括号在节点\(j\),有\(f[i]=1+f[fa[j]]\)

我们只需要开一个全局栈对括号进行匹配

对于每个\(si\),\(Ans_{si}=\sum_{j\text{在1-i路径上}} f[j]\)

对此我们只需要记录一个前缀和即可

时间&空间复杂度\(\rm O(N)\)

Code


P2279 [HNOI2003]消防局的设立

本题做法较多,有\(\rm DP\),贪心等,时间复杂度从$\rm O(N^2) \(到\)\rm O(N) $都有。

这里介绍最优的贪心算法。

一个不难想到的贪心就是每次覆盖最深的节点。因为最深的节点必须覆盖,而不同的最深的节点覆盖的先后顺序没有影响。

所以我们需要支持标记一个点,并支持查询一个点距离\(2\)的范围内是否有点被标记。

我们只用记录每个节点是标记,子节点是否标记,孙子节点是否标记即可。

桶排可以做到线性时间复杂度。

Code


P5659 [CSP-S2019] 树上的数

\(\rm CSP/NOIP\)最难的题。

这道题有两种不同的思维路线,得到两种不同的方法。

第一种:菊花图。

观察一下,发现删完后所有数字构成一个单环\(a_1\to a_2\to \cdots\to a_n\to a_1\),每个箭头表示数字的最终移动方向。

所以我们贪心移动,避免提前成环即可,用并查集维护。

同理对于任意树,把每个节点拆出来,与它相邻的所有数组最终也一定构成一个单环,对每个节点维护一个并查集即可。

时间复杂度\(\rm O(N^2\log N)\)

第二种:链

观察一下,发现如果链上一点移动到另一点,则路径上所有边的先后顺序是固定的。

同理对于任意树,把每次移动路径拿出来,则路径上的边的现后顺序也是固定的,我们可以用链表维护这些边的先后顺序。

时间复杂度\(\rm O(N^2)\)。

Code


P5666 [CSP-S2019] 树的重心

首先一颗树的重心最多只有两个。

每个点向重心移动方向是固定的,所以我们可以倍增优化。

考虑断开链的影响,需要二次扫描换根。

Code


CF1486F Pairs of Paths

给定\(M\)个路径,求相交恰好为一个点的路径对数。

结论,两个路径如果相交则交一定过一个路径的\(\rm LCA\),且是较深的\(\rm LCA\)。

考虑分开算贡献,分为\(\rm LCA\)相同时的贡献,和\(\rm LCA\)不同时的贡献。

我们对每条路径按\(\rm LCA\)深度排序,对于第一种开桶计算贡献,后者我们用树状数组维护单点加子树和即可。

Code


P6776 [NOI2020] 超现实树

四种不同形态的子树可以合成一个\(\rm End\)节点,所以我们分层递归下去分别判断四种情况即可。

Code

上一篇:LeetCode-21.合并两个有序链表(链表+递归)


下一篇:Pr 入门教程如何确保剪辑保持同步?