『从入门到入土』树链剖分学习笔记

# **目录** * [0. 前言](#0) * [1. 附题单](#1) * [2. 重链剖分基础](#2) * [2.1. 重剖求 LCA](#21) * [2.1.1. 引入](#211) * [2.1.2. 定义](#212) * [2.1.3. 时间复杂度](#213) * [2.1.4. 实现](#214) * [2.2. 重剖维护树上修改查询](#22) * [2.2.1. 如何转化](#221) * [2.2.2. 实现](#222) * [2.3. 基础题选讲](#23) * [2.3.1.[ABC294G] Distance Queries on a Tree 边转点技巧](#231) * [2.3.2.P4116 Qtree3 思路转化](#232) * [3. 进阶提高篇（重链剖分的一些套路）](#3) * [3.1. P5838 [USACO19DEC] Milk Visits G 动态开点+多颗线段树](#31) * [3.2. Jamie and Tree 换根树剖](#32) * [3.3. P3401 洛谷树 拆位统计](#33) * [3.4. P7735 [NOI2021] 轻重边 染色+计数](#34) * [3.5. Dynamic Diameter 线段树上的奇怪 pushup](#35) * [3.6. Drivers Dissatisfaction MST 相关](#36) * [3.7. P2542 [AHOI2005] 航线规划 图转树+离线操作](#37) * [3.8. ...Wait for it... 树上拆点维护](#38) * [3.9. P5138 fibonacci 树上点权套斐波那契数列套矩阵快速幂](#39) * [3.10.P4175 [CTSC2008] 网络管理 重剖+整体二分](#310) * [3.11.Noble Knight's Path 重剖+主席树+二分](#311) * [3.12.Moonwalk challenge 重剖+二分+hash](#312) * [3.13.Tourists 圆方树上重剖+multiset 存信息维护](#313) * [3.14.GSS7 - Can you answer these queries VII 重剖+最大子段和](#314) * [3.15.P3925 aaa被 续 思路转化+重剖](#315) * [3.16.Tree or not Tree 基环树+重剖](#316) * [3.17.P9808 [POI2022~2023R1] zbo 推式子转化+重剖](#317) * [3.18.P4719 【模板】"动态 DP"&动态树分治 ddp](#318) * [3.19.瓦里奥世界 Rujia Liu loves Wario Land! 启发式合并树剖](#319) * [3.20.P7671 [GDOI2016] 疯狂动物城 推式子+维护进阶版](#320) * [3.21.P9620 歌姬 树剖魔改 dfn 序](#321) * [3.22.MEX Tree Manipulation ddp 思想+找性质](#322) * [3.23.后记](#323) * [4. 长链剖分](#4) * [4.1. 定义](#41) * [4.2. 实现](#42) * [4.3. 应用（板子）](#43) * [4.4. 应用（长剖优化 dp）](#44) * [4.5. 后记（个人关于长剖看法）](#45) * [5. 平衡树部分（Splay）](#5) * [5.1. 二叉搜索树](#51) * [5.1.1. 定义](#511) * [5.1.2. 应用](#512) * [5.1.3. 时间复杂度](#513) * [5.2. 平衡树](#52) * [5.2.1. 定义](#521) * [5.2.2. 如何维护平衡](#522) * [5.2.3. 操作实现](#523) * [6. 实链剖分（LCT）](#6) * [6.1. 定义](#61) * [6.2. 实现](#62) * [6.3. 应用（板子）](#63) * [6.3.1.DYNALCA - Dynamic LCA LCT 求 LCA](#631) * [6.4. 应用（技巧）](#64) * [6.4.0.P3203 [HNOI2010] 弹飞绵羊 轻量化 LCT](#640) * [6.4.1./6.1.2.P4172 [WC2006] 水管局长 LCT 维护边权+MST+倒序操作](#641/642) * [6.4.3.P4319 变化的道路 线段树分治+动态 MST](#643) * [6.4.4.P2542 [AHOI2005] 航线规划 LCT 求动态割边/6.4.5.P5622 [DBOI2019] 巫女的职责 LCT 求动态割点](#644/645) * [6.4.6.P4219 [BJOI2014] 大融合 LCT 维护子树信息](#646) * [6.4.7.P4271 [USACO18FEB] New Barns P LCT 维护直径](#647) * [7. 资料来源鸣谢](#7) **P.S.:洛谷文章区有了自带的目录！** * * * # -1.Update 目前工程：在更新重剖的一些 trick 和 LCT 的一些 trick，目前每天沉浸式写题。 LCT 可能会拖更很久吧。 完工后会删掉这个部分。 * * * # **0.前言** * **Warning：打开这篇文章前最好确保自己已经学过了倍增，树上差分，dfs序等知识点。一定要学过线段树！！！** 写这篇文章的主要目的是为了介绍树链剖分以及树链剖分的一些模型。 可能你们也注意到了，这篇文章的标题是 **『从入门到入土』树链剖分**。 而不是重链剖分或 LCT。旨在一次性从重链剖分开始讲到 LCT 结束。 那么，在正式开始之前，先写下致谢吧： * 带我进树剖坑的大佬 [lzyqwq](https://www.luogu.com.cn/user/539211)。这里提供的题单的前身也正是他的博客中的树剖题单捏。 * 同时感谢让我学会了长剖的[树剖姐姐 Ynoi](https://www.luogu.com.cn/user/124721) 的[博客](https://www.luogu.com.cn/blog/Ynoi/zhang-lian-pou-fen-xue-xi-bi-ji)。 * 还有 LCT 的题单前身正是大佬 [zhiyangfan](https://www.luogu.com.cn/user/137603) 的 LCT题单。 * 最后鸣谢下让我学会了 LCT 的大佬 [FlashHu](https://www.luogu.com.cn/user/61325) 的博客 $\LARGE{希望大家都能在看完后学会树剖!}$ ------------ # **1.附题单** [『基础篇』重链剖分](https://www.luogu.com.cn/training/440256) [『应用（折磨）篇』重链剖分](https://www.luogu.com.cn/training/440258) [『究极折磨篇』LCT 题单](https://www.luogu.com.cn/training/440260) * * * # **2. 重链剖分基础** ## 2.1. 重剖求 LCA ### 2.1.1. 引入 重剖，与树相关，在树上的他，有一个最基础也是最重要的作用：[**求 LCA**](https://www.luogu.com.cn/problem/P3379)。 求 LCA 可谓是树上最基础也是最重要的部分了，基本所有的树上询问与路径有关的问题，都会考虑拆成 **$u\longrightarrow lca,lca\longrightarrow v$** 的方式来进行计算。 想必大家都会倍增求 LCA 吧，他的方法就是尝试往上跳 $2^j$ 步，然后从大到小枚举 $j$。像二进制拆分一样把需要跳的步数变为二进制下的 $0,1$ 来跳，就可以保证 $\log{n}$ 的复杂度。 对于重链剖分而言，则是需要找到另一种跳跃的方式，使得跳跃的步数可以压缩，使得最终复杂度为 $O(n\log{n})$。 正如他的名字一般，重剖所采取的方法，就是把一颗树剖成一条条的重链，以一次至少跳掉一条重链的方式来保证其复杂度。 ### 2.1.2. 定义 了解了重链剖分的原因之后，我们就可以正式开始学习重链剖分了。 先给出几个定义以及一张图（参考资料 [OI Wiki](https://oi-wiki.org/graph/hld/)）： * 定义 **重子节点** 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。 * 定义 **轻子节点** 表示剩余的所有子结点。 * 从这个结点到重子节点的边为 **重边**。 * 到其他轻子节点的边为 **轻边**。 * 若干条首尾衔接的重边构成 **重链**。 * 把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。  个人认为，对于上面把落单的节点也看做重链还有一种解释方式，即： * 重链的定义为若干条首尾相连的重边顶端，接上一条轻边。（除了根节点上接出的第一条重链） 那么落单的节点的情况便变为了『若干』 为 $0$ 的情况。 ### 2.1.3. 时间复杂度 这么定义是有原因的，我们容易证明，一个点一直往上跳，最多只会经过 $\log{n}$ 条重链。 下面给出证明： * 考虑从最上面的根节点开始往下走。 * 最开始的子树大小即为 $n$。因为共有 $n$ 个节点。 * 而当我们每走过一条 **轻边** 的时候，子树大小至少会减半（不然这条边就变成重边了）。 * 那么从子树大小 $n$ 开始减小至 $1$ 的复杂度便是 $\log{n}$，也就是最多只会经过 $\log{n}$ 条轻边。 * 证毕。 ### 2.1.4. 实现 接下来，考虑顺推的思路，既然经过轻边的次数已经被保证了，也就意味着，一条路径最多只会被拆分为 $\log{n}$ 条重链，接下去，我们只需要保证路过一条重链的复杂度为 $O(1)$ 即可。 先把上面那张图拿下来，方便讲下。  P.S.:下文所提之编号指的是图中的 dfn 序 比如对于节点 $2,4$ 的 LCA。因为他们在同一条重链中，显然就是其中深度较浅的一个节点。写成代码的形式就是。 if(top[x]==top[y]) { if(dep[x]<dep[y]) return x; else return y; } 这里的 $top$ 指的是当前节点的重链顶端，因为每个点所属的重链显然不能重复，（也就是重链将树完全剖分。）所以我们可以直接用这个点所属重链顶端的节点编号是否相同来判断是否属于同一重链。 而 $dep$ 指的便是这个节点在树中的深度。 接着，我们再来考虑当 $u,v$ 不属于同一条重链时的情况，结合前面所提到的 * 『我们只需要保证路过一条重链的复杂度为 $O(1)$ 即可』 我们很容易发现，当 $u,v$ 不在同一条重链时，这两条重链中至少有一条是没有贡献了的。 * **也就是 LCA 至多只会出现在其中的一条重链中。** 那么我们便可以直接跳过其中的一条重链。 那么到底是跳过那一条呢？ 显然不是根据当前节点的深度判断的，而是根据 * **链顶的父节点**的深度决定的。 说起来有点抽象，但是我可以举一个图里面的例子。 如下图（没想到吧还是他）：  其中编号为 $10$ 的节点**链顶的父节点**便是 $2$ 号节点。 写成代码的形式也就是： fa[top[x]] 其中 $fa$ 数组代表当前节点的父亲节点。 跳了一次之后怎么考虑呢？ * 回到刚刚开头判断是否在同一条重链中的情况即可，如果找到了就结束循环，否则继续判断。 下面给出树剖求 LCA 的完整代码： int LCA(int x,int y) { while(top[x]!=top[y]) { if(dep[fa[top[x]]]<dep[fa[top[y]]]) swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); return x; } 现在，我们已经学会了树剖求 LCA 的方法，但是，如果光光使用上面这个代码，我们会发现一个非常严重的问题。 就是： * 我们的 $fa,dep,top$ 数组都未曾定义求过值。 考虑如何进行预处理，得出我们所需要的这些值。 * * * 因为是重链剖分，所以我们肯定要求出每个节点的子树大小，以及他所连的重儿子是谁。 数组的名称与意义说明： * $\mathrm{fa_i}$ 代表 $i$ 节点的父亲节点，特殊的，根节点没有父亲。 * $\mathrm{dep_i}$ 代表 $i$ 节点的深度，特殊的，根节点的深度为 $1$。 * $\mathrm{si_i}$ 代表 $i$ 节点的子树大小，特殊的，叶子节点的子树大小为 $1$。 * $\mathrm{son_i}$ 代表 $i$ 节点的重儿子编号，特殊的，叶子节点没有重儿子。 * $\mathrm{top_i}$ 代表 $i$ 节点的重链顶端节点编号，特殊的，重链顶端节点的 $\mathrm{top}$ 数组值为他本身。 实现时，我们考虑使用 dfs，第一次处理出 $\mathrm{fa,dep,si,son}$，第二次处理出 $\mathrm{top}$。 正常情况下，我们考虑以 $1$ 节点为根节点进行剖分。 写成代码就是（这里使用的是链式前向星就不多做解释了）： void dfs1(int u,int ff)//ff是当前节点的父亲 { fa[u]=ff,si[u]=1,dep[u]=dep[ff]+1; for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(v==ff) continue; dfs1(v,u);si[u]+=si[v]; if(si[son[u]]<si[v]) son[u]=v; } } void dfs2(int u,int topf)//topf是当前重链顶端 { top[u]=topf; if(son[u]) dfs2(son[u],topf); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(v==fa[u]||v==son[u])continue; dfs2(v,v); } } 注意到这里的代码都挺好理解的，除了 dfs2 中的 if(son[u]) dfs2(son[u],topf); 显然，判重儿子这一步可以放进循环里来单独判断，但这里为什么要拿出来呢？ 这里我先卖个关子先，这和之后树剖结合数据结构有密切联系。 那么有了两遍 dfs 的预处理后，树剖便能完成 $O(m\log{n})$ 的复杂度完成[**求 LCA**](https://www.luogu.com.cn/problem/P3379) 了。 [『模板』求 LCA 的 std](https://www.luogu.com.cn/paste/daml9iuj)。 * * * ## 2.2. 重剖维护树上修改查询 ### 2.2.1. 如何转化 上一块引入部分，我们讲了重剖求 LCA 的方式，但是，重剖的用途远不止此。 要是重剖只能求 LCA 的话，还不如魏老师的**好写好调且小常** $O(n\log{n})$ dfs 序大法呢。 所以接下来，我们要在树剖上套上数据结构，具体的例题便是[重剖模板](https://www.luogu.com.cn/problem/P3384)。 在这题里面，我们发现询问的东西，有了了 $u,v$ 路径上的点权和。 而操作里面，也增加了修改一条链上的点权值。 （另外两种操作我们先暂且不考虑，优先考虑这两种。） 这个时候我们会想到什么呢？ 要是询问的变成了一个区间，修改的也是一个区间和的话，就可以用线段树方便处理了。 那么我们怎么把树上路径转化为与区间相关的东西呢？ 链不就能压为是一个区间吗，那我们只需要把树上路径转化为一条条链即可。 那怎么转化为链呢，这不就是重剖吗。 至此转化的问题已经解决了，但是还有一个问题：我们的线段树不是有一个序列的编号吗，那我们从树中拿下来的链编号怎么定呢？ 这个时候就要涉及到 dfs 序了，还记得之前卖的那个关子吗（不记得回去看一下）。 * 我们把重儿子的遍历放在前面就是为了保证**同一条重链的编号连续！** 那么，我们的 dfs2 就要加上两个数组，他们是： * $\mathrm{dfn_i}$ 代表的是 编号 $i$ 的这个节点他的 dfs 序。 * $\mathrm{id_i}$ 代表的是 dfs 序为 $i$ 所对应的节点编号。 写成代码也就是： void dfs2(int u,int topf) { top[u]=topf;dfn[u]=++cnt,id[cnt]=u; if(son[u]) dfs2(son[u],topf); for(int i=head[u];i;i=e[i].nxt) { int v=e[i].v; if(v==fa[u]||v==son[u])continue; dfs2(v,v); } } 至此，我们就保证了同一条重链上的 dfs 序连续，可以用这个序来作为线段树的区间下标了。 也就如上面那个图一样：  * * * ### 2.2.2. 实现 首先考虑实现路径转链的操作，根据之前的理解和观察不难发现，其实我们求 LCA 时跳过的一条条链就是我们分割出来的一条条链。所以，写成代码就是： int query(int u,int v) { int res=0; while(top[u]!=top[v]) { if(dep[top[u]]<dep[top[v]]) swap(u,v); res+=query(1,dfn[top[u]],dfn[u]);res%=mod; u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); res+=query(1,dfn[u],dfn[v]);res%=mod; return res; } 其实这个代码和 LCA 出入不大了，我们放一块对比一下试试： int LCA(int x,int y) { while(top[x]!=top[y]) { if(dep[fa[top[x]]]<dep[fa[top[y]]]) swap(x,y); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); return x; } 会发现，其实我们的询问只是把在跳的过程中每条重链的值累加上来了罢了。 * **Warning:这里尤其要注意在线段树查询操作中的询问区间一定是小的写在前面，也就是深度小的点写在前面！** 接着的修改操作 modify 与其区别不大，唯一的区别只是把 query 改为了 modify 罢了。 回归原题目，想起来还有两种操作是子树权值加和子树权值和查询，比起前面的路径操作，这个明显简单了许多，因为是 dfs 序，所以子树里的序号显然是连续的，直接区间修改查询即可。 最后是[重剖模板 std](https://www.luogu.com.cn/paste/intvy0te)。 $\large{截止这里,你已经学会了最基础的树链剖分了,接下去,打开上面题单中的基础篇进行一些练习吧!}$ 树剖主要就是码量比较逆天，还是很需要练习的。 ------------ ## 2.3. 基础题选讲 这里主要讲解一些蓝即以下的基础题捏，适合刚入门树剖的萌新看看。 **P.S.:这里的题主要还是以码量为主，思路还都不是很难的，一定要自己上手练习。** 那就直接开始吧。 ------------ ### 2.3.1.[[ABC294G] Distance Queries on a Tree](https://www.luogu.com.cn/problem/AT_abc294_g) 边转点技巧 题意已经非常清楚了，在此不再过多赘述。 这个时候我们会发现这道题他修改的是边权不是点权，好像无法维护了？ 实际上，我们不难想到一种方法，将边权转为点权，而这种方法，也就是**边转点技巧**。 那对于一条边而言，我们的边权应该放到哪个节点上呢？ 应该是下面的那个节点吧，那么我们就完成了边转点的操作。 对于查询呢？ 这个时候要注意一个判断，因为我们把边权转点权了。所以 $u,v$ 的 LCA 需要特判。 LCA 的点权是他上面的一条边的边权。 显然这个是查询不到的，所以**千万不要加上！** 那么边转点就算是说完了，可以先写个练习下。 倍增写的就不附了。 $\large{练习题}$ [P4315 月下“毛景树” ](https://www.luogu.com.cn/problem/P4315) 正常的边转点之后，链赋值，链加。 然后线段树中维护最大点权即可。 （std 不附了，写的很抽象）。 [P4114 Qtree1](https://www.luogu.com.cn/problem/P4114) 这道题首先是正常的边转点，然后接着的操作就变为了单点修改以及链查，还是很简单的。 当然做完后也可以尝试下[QTREE - Query on a tree](https://www.luogu.com.cn/problem/SP375)，这题是只能交 C 语言，可以练习下 C++$\rightarrow$C。 [P3038 [USACO11DEC] Grass Planting G](https://www.luogu.com.cn/problem/P3038) 这道题就先正常边转点，然后 $u\rightarrow v$ 的路径上点权全部 $+1$，查询时直接拿 $v$ 的点权即可。 --------------- ### 2.3.2.[P4116 Qtree3](https://www.luogu.com.cn/problem/P4116) 思路转化 这道题呢，主要是一个思路上的转化。 我们先看下题，他查询的是 $1\rightarrow v$ 上的第一个黑点，这种东西该怎么操作呢？ 我们发现，从 $1\rightarrow v$ 路径上的点，他的 dfs 序是单调递增的，也就是第一个黑点绝对是 dfs 序最小的。 所以我们考虑给每个黑点赋值为他自己的 dfs 序的值，每个白点赋值为 INF。 如此一来，题目中的查询第一个黑点就变成了查询 $1\rightarrow v$ 上的最小值。 （代码就不贴了，我用 set 写的。） * * * # 3. 进阶提高篇（重链剖分的一些套路） 看到这里说明你已经理解了重剖而且写过了一定的基础码量题，现在，你可以开始真正应用重剖了。 本章节将会讲一些重剖中比较模板的套路或是好题，方式是结合例题分析。 * **Warning:从此段开始难度直线上升，至少是上位蓝。** * **P.S.：如果找不到锅了可以对下我的[出锅合集](https://www.luogu.com.cn/paste/ahc7lu2i)。** 题目讲解排序按照难度不一定单调递增。 那就开始吧： * * * ### **3.1. [P5838 [USACO19DEC] Milk Visits G](https://www.luogu.com.cn/problem/P5838) 动态开点+多颗线段树** 这题有个弱化版，可以先考虑下[弱化版](https://www.luogu.com.cn/problem/P5836)。 简要题意： 给定一颗树，树上每个点有个点权，询问 $u,v$ 的路径上有没有给定的点权出现过。 首先考虑下弱化版先，发现弱化版点权只有两种，所以直接考虑分类讨论，不同的查找分类讨论一下处理。 或者是直接暴力做，给线段树里面加入这个区间是否有其中一种奶牛的标记就可以简单秒杀了。 接着来考虑金组的加强版，有 $10^5$ 种点权，处理便困难起来了，如果像之前那样直接暴力做，想都不用像就会挂了。 所以我们考虑使用 STL 大法，因为题目只让我们判断有没有而不问个数，所以我们可以直接套上一个 set。 题目中也没有修改操作，所以 set 十分好维护，只要在造的时候加进来就可以了。 复杂度 $O(n\log^3{n})$。 附 [std](https://www.luogu.com.cn/paste/mxt6l17d)。 显然这种做法不是很优，所以我们考虑一种优化的思想： 对着每一种颜色开一颗线段树，查询便变成了在对应颜色的线段树上查找是否出现过。 显然如果我们直接开 $10^5$ 颗线段树空间会一言难尽，所以我们考虑用动态开点线段树维护，每个颜色也开个根节点。 （因为我懒所以就不再自己写代码了，可以参考下题解中神犇 lzyqwq 的代码。） $\large{练习题}$ [P3313 [SDOI2014] 旅行](https://www.luogu.com.cn/problem/P3313) 这个题挺显然的，只是有点难写。 [std](https://www.luogu.com.cn/paste/qubeyzat)。 [[ABC133F] Colorful Tree](https://www.luogu.com.cn/problem/AT_abc133_f) 这个题只需要注意下每次并不是真的修改。 所以每次只要查找**给定颜色的边的总权值**。 然后用原本的权值，减去**给定颜色的边的总权值**再加上**给定颜色的边的数量**乘以**更改后的边权**即可。 [std](https://www.luogu.com.cn/paste/5fgry5oj)。 [GOT - Gao on a tree](https://www.luogu.com.cn/problem/SP11985) 刚刚讲的那题，但是多组数据，卡掉了 $O(n\log^3{n})$ 的做法。 这边建议写成刚刚讲的那种方法，而不是 $O(n+m)$ 的强大方式，当然这个方式最好也写下。 [Santa's Gift](https://www.luogu.com.cn/problem/CF960H) 期望题，先展开下式子，然后因为颜色限制，所以考虑多颗线段树开拆即可。 [std](https://www.luogu.com.cn/paste/id2ofcy4)。 [Caisa and Tree](https://www.luogu.com.cn/problem/CF463E) > * 「保证 $2$ 操作的数量不超过 $50$」的限制和 $10$ 秒的时限太不牛了。让我们去掉这个限制并将时限改为 $2$ 秒，再考虑怎么做。 > * by lzyqwq 这里使用和神犇相同的做法谢谢喵。 考虑把质因数拆出来，不同质因数的树开一颗就行了。 [std](https://www.luogu.com.cn/paste/grd0254h)。 * * * ### **3.2. [Jamie and Tree](https://www.luogu.com.cn/problem/CF916E) 换根树剖** 这道题是一个非常典的案例，这种题我称为**换根树剖**。 和他的名字一样，他的主要操作就是**换根树剖**。 也就是，这棵树的根可能会变，而他的查询，也是和子树有关。 碰到这种没有碰过的套路题一定不要慌，仔细观察一下很容易得出： 这不就**分类讨论**吗？ 我们肯定不能每次换根每次重构，所以我们设定的那个根不妨称之为假根（正常应该都设置为 $1$ 吧），那真正的根和假根会导致什么误差呢？ 只有子树会有部分不同吧，那分类讨论即可： （这里复制了[神犇 Farkas_W](https://www.luogu.com.cn/blog/Farkas/guan-yu-shu-lian-pou-fen-huan-gen-cao-zuo-bi-ji) 里面的讲解图片（自己花真的要累死的）分隔线内是复制内容+更改捏） * * * 一.当 $lca(x,y)=x$ (这里满足 $x$ 的深度更小)  $\quad$ $1$. $root$ 在 $x$ 的子树中，也在 $y$ 的子树中，即 $lca(x,root)=x$ && $lca(y,root)=y$ ，此时 $LCA(x,y)$ 是 $y$ ，因为图要反过来看(以 $root$ 为根) $\quad$ $2$. $root$ 在 $x$ 的子树中，但不在 $y$ 的子树中，即 $lca(x,root)$ ，此时 $LCA(x,y)$ 是 $lca(y,root)$。 $\quad$ $3$. 其他情况下， $LCA(x,y)$ 就是 $x$ 。 二.当 $lca(x,y)!=x$ (因为 $x$ 的深度更小，所以 $lca(x,y)!=y$，且 $x,y$ 在不同子树上)  $\quad$ 1. ( $lca(x,root)=x$ )||( $lca(y,root)=y$ ),root在x(或y)的子树中时， $LCA(x,y)$ 为 $x$ (或 $y$ )，显然。 $\quad$ 2. ( $lca(x,root)=root$ && $lca(x,y)=lca(y,root)$ )||( $lca(y,root)=root$ && $lca(x,y)=lca(x,root)$)，即 $root$ 在 $x$ 到 $y$ 的简单路径上时，答案为 $root$ 。(也可以用深度判断， ( $lca(x,root)=root$ && $dep[root]>=dep[lca(x,y)]$ )||( $lca(y,root)=root$ && $dep[root]>=dep[lca(x,y)]$ )) $\quad$ 3. $lca(x,root)=lca(y,root)$ ，即 $root$ 在上方时，$LCA(x,y)$ 为 $lca(x,y)$ 。 $\quad$ 4. 当 $root$ 在$x$，$y$ 的链上节点的子树中时， $LCA(x,y)$ 为那个链上节点。 $\quad$这样就把树上所有 $root$ 位置的情况都考虑到了，不重不漏。 $$\text{子树修改(查询)}$$  $\quad$ $1$. 当 $x=root$ 时， $x$ 就是此时整棵树的根，那么就是全局修改(查询)。 $\quad$ $2$. 当 $root$ 在x子树中时，就需要特别判断了，根据图像我们可以发现此时x的真正子树是包括除了 $root$ 方向上的子树之外其他所有节点。 $\quad$ $3$. 其他情况下 $x$ 的子树以 $root$ 为根和以 $1$ 为根是一样的。 * * * 分类讨论之后这题就直接秒杀为正常树剖了，附上 [std](https://www.luogu.com.cn/paste/v02sccvn)。 $\large{练习题}$ [P3979 遥远的国度](https://www.luogu.com.cn/problem/P3979) 这个是真的基本没区别，也没什么好说了，自己好好写一遍应该就能真正记住了。 [std](https://www.luogu.com.cn/paste/uyws54un)。 * * * ### **3.3. [P3401 洛谷树](https://www.luogu.com.cn/problem/P3401) 拆位统计** 这题也是一个比较套路的操作，就是拆位。 考虑把每一位的 $0,1$ 情况拆出来考虑，就成了正常的题目了。 附上 [std](https://www.luogu.com.cn/paste/kuunmriz)。 $\large{练习题}$ [P5354 [Ynoi2017] 由乃的 OJ](https://www.luogu.com.cn/problem/P5354) 不过这题用拆位的方法不能过（或许可以卡常卡过去？），纯当练习好了。 * * * ### **3.4. [P7735 [NOI2021] 轻重边](https://www.luogu.com.cn/problem/P7735) 染色+计数** 最折磨的典中典，这题是真的好，他应该不能算是一个固定的套路，但是好题还是讲一下吧。 * 我们考虑给每一次操作的两个端点染上独一无二的颜色。 没有太懂的话，具体的讲一讲，因为要将一条路径上的边修成重边，那么路径点染同色的操作就可以保证这条路径上**点同色且所有边两端点同色**，这样这些边就符合重边的判定了。 由于这些点被染成的是一种**独一无二的颜色**，是一定不与前面的颜色重复的，所以所有染色点连边的另一端一定与它的颜色不同，这样子这些边就自然而然的变成了轻边。 所以就美妙转化掉了，成了如何统计树的一段路径上**同色相邻点对**的数量。 这个时候就来考虑线段树维护了，但是由于重链相连接的地方可能会产生贡献，所以我们写的时候要分开写，也就是左边跳左边的，右边跳右边的。 给个代码看看吧： int query(int x,int y) { bool flag=0; tree h,ans1=(tree){0,0,0,0,0,0},ans2=(tree){0,0,0,0,0,0}; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) flag=!flag,swap(x,y); h=query(1,dfn[top[x]],dfn[x]);//cout<<h.sum<<" "<<x<<" "<<y<<endl; if(flag) ans2=(tree){0,0,h.cl,ans2.cr,ans2.sum+h.sum+(ans2.cl==h.cr),0}; else ans1=(tree){0,0,ans1.cl,h.cl,ans1.sum+h.sum+(ans1.cr==h.cr),0}; x=fa[top[x]]; } if(dep[x]<dep[y]) swap(x,y),flag=!flag; h=query(1,dfn[y],dfn[x]); if(flag) ans2=(tree){0,0,h.cl,ans2.cr,ans2.sum+h.sum+(ans2.cl==h.cr),0}; else ans1=(tree){0,0,ans1.cl,h.cl,ans1.sum+h.sum+(ans1.cr==h.cr),0}; return ans1.sum+ans2.sum+(ans1.cr==ans2.cl); } 也就是左边是 $ans1$ 右边是 $ans2$。 最后附上代码 [std](https://www.luogu.com.cn/paste/qhuuq43t)。 $\large{练习题}$ [P2486 [SDOI2011] 染色](https://www.luogu.com.cn/problem/P2486) 这个是双倍经验吧。 * * * ### **3.5. [Dynamic Diameter](https://www.luogu.com.cn/problem/CF1192B) 线段树上的奇怪 pushup** **这题，真的，是，太痛苦了！** 我不知道刚学重剖的我当时怎么想的写了这个题，这个题是真的很痛苦。 题意很显然的，求直径的话我们可以弄两颗线段树，一个是维护的节点间距离，一个维护的是 $dfn$ 在这个区间内的树的直径大小。 很显然对吧，接着就是痛苦实现了，这题的唯一痛苦就在实现上。 考虑下如何合并第二颗线段树中的值，也就是答案线段树中的值。 一颗树的一条直径是两个点之间的一条路径对吧，那两个子树就有两条直径四个点对吧。 这边可以证明出来最后树的直径肯定是在这四个点中两两组合中取一个最大。 请读者自行尝试证明一二。 接着有了这个之后我们只需要算出来两点距离就行了，拿另一颗线段树查询就完了。 **真的很暴力！** 附上 [std](https://www.luogu.com.cn/paste/c5r2crro)。 $\large{练习题}$ [P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并](https://www.luogu.com.cn/problem/P4556) 线段树合并板子，可以学下挺好的。 [std](https://www.luogu.com.cn/paste/lefojdxa)。 [P4679 [ZJOI2011] 道馆之战](https://www.luogu.com.cn/problem/P4679) 这个合并的东西有点不一样，是二维的好玩。 [std](https://www.luogu.com.cn/paste/yij6cff9)。 [P9555 「CROI · R1」浣熊的阴阳鱼](https://www.luogu.com.cn/problem/P9555) 这题合并的时候**注意顺序！注意顺序！！注意顺序！！！** [std](https://www.luogu.com.cn/paste/m0gx4bg5)。 [Tavas on the Path](https://www.luogu.com.cn/problem/CF536E) 这题折磨的，一定要做好心理准备。 [std](https://www.luogu.com.cn/paste/gn00zmzk)。 [Moonwalk challenge](https://www.luogu.com.cn/problem/CF1045J) 这题使用奇怪 pushup 的做法可以直接把整段的字符串弄出来然后再数次数。 虽然过不了，但是练习码力还是很好的。 * 如果说你用的是 find 查询次数，那写到最好情况应该是 TLE on #15。 * 如果你写的是 hash 查询次数的话，那最好应该是写到 RE on #4。 亲身实践得到的/cf。 [std（使用 find 实现的 TLE on #15）](https://www.luogu.com.cn/paste/268oot4l)。 [std（使用 hash 实现的 RE on #4）](https://www.luogu.com.cn/paste/xaizjxb6)。 * * * ### **3.6. [Drivers Dissatisfaction](https://www.luogu.com.cn/problem/CF733F) 重剖+MST** 这题看到后我们会有一个比较显然的想法，把钱全部花在一条边上，因为如果我花在两条边上，不如花在一条代价更小的边上。 他相当于是固定了一条边肯定要在树中的最小生成树，参考[板子严格次小生成树](https://www.luogu.com.cn/problem/P4180)中的做法，先求最小生成树然后考虑换边即可。 $\large{练习题}$ [Best Edge Weight](https://www.luogu.com.cn/problem/CF827D) 讲解见[文章](https://www.luogu.com.cn/blog/Hok/solution-cf827d)了，其实我感觉这题挺像动态 MST 的？ [MST Unification](https://www.luogu.com.cn/problem/CF1108F) [std](https://www.luogu.com.cn/paste/0vtpzwd1)。 [Edges in MST](https://www.luogu.com.cn/problem/CF160D) [std](https://www.luogu.com.cn/paste/kgv78zbw)。 （鬼知道我为什么写了 $6.2$ KB，仔细一看原来是板子人） * * * ### **3.7. [P2542 [AHOI2005] 航线规划](https://www.luogu.com.cn/problem/P2542) 图转树+离线操作** 里面保证了这么一句话：在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。题目保证不存在重边，而且互相连通，又是无向图...想到了什么？ **图可以变为树啊**！也就是说，我们需要动态的维护树上点之间的距离。 然后树剖维护树上的边权，这样就可以轻而易举的求出树上两点之间的距离了。 直接将一个环内的点之间的边权赋为 $0$ 不就行了！ 读入询问，逆序处理。 先随便在原图中求出一棵生成树。 然后用那些没被删除的非树边先更新一遍当前的边权。 最后树剖猛猛做。 注意经典边转点细节，不要修改 **LCA!!!!!!** 附上 [ std](https://www.luogu.com.cn/paste/2nu9yt12)。 ##### **练习题** [OTOCI - OTOCI](https://www.luogu.com.cn/problem/SP4155) [P4312 [COI2009] OTOCI](https://www.luogu.com.cn/problem/P4312) 两题通用 [std](https://www.luogu.com.cn/paste/1pze1pfl)。 **P.S.：这两题是没有强制在线，原题是用交互保证在线的，现在可以离线！** [P3950 部落冲突](https://www.luogu.com.cn/problem/P3950) [std](https://www.luogu.com.cn/paste/tgzbawuv)。 * * * ### **3.8. [...Wait for it...](https://www.luogu.com.cn/problem/CF696E) 树上拆点维护** 考虑第一篇题解里的做法，把每个点拆成出点和入点，权值为无穷大。 接着一个物品单独造一个点，和他前面后面的点连起来。 对于查询而言的话，就是暴力每次扫一个删一个。 复杂度因为是删掉物品，所以可以保证。 **很简单对吧，特别难调！** 附上 [std](https://www.luogu.com.cn/paste/07zjxbdp)。 $\large{练习题}$ [P5478 [BJOI2015] 骑士的旅行](https://www.luogu.com.cn/problem/P5478) [std](https://www.luogu.com.cn/paste/xxqtscp8)。 [Duff in the Army](https://www.luogu.com.cn/problem/CF587C) 这三题好像没有什么区别/kk。 * * * ### **3.9. [P5138 fibonacci](https://www.luogu.com.cn/problem/P5138) 树上点权套斐波那契数列套矩阵快速幂** 这题的话，我认为主要的重点是一个结论的背诵。 也就是: $$f_{m+n}=f_{m-1}\times f_n+f_m\times f_{n+1}$$ 这个结论非常重要，基本涉及 fibonacci 数列的题大概率用到吧。建议熟背。 有了结论之后我们就可以开拆式子了。 首先把 $u,v$ 的距离弄出来，考虑下用与根的距离算，也就是 $dis_u-dis_v+k$。然后用上面那个公式给式子拆开做即可。 也就是令 $m=dis_u,n=k-dis_v$ 之后换算式子，左右当做两个 $tag$ 写就可以了。 附上 [std](https://www.luogu.com.cn/paste/nx9b8q15)。 * * * ### **3.10.[P4175 [CTSC2008] 网络管理](https://www.luogu.com.cn/problem/P4175) 重剖+整体二分** 这道题是我第一次接触整体二分/kk。 首先概括下题意：带修改树链第 $k$ 大问题。 应该算是一个经典问题了。 首先说下整体二分，就是用分治的思想一次性完成所有的操作，其中包括了修改与查询等。最后一次输出。 这道题也就是相当于把整体二分上树。 考虑把每个操作都标记一个时间戳 $cntt$，保存在操作记录数组 $t$ 中。 由于树初始带有点权，所以就相当于初始单点修改了 $n$ 次，把每个点改为对应的点权。 更改点权就相当于先删除后增加点权了。 剩下的就是整体二分的套路了。 附上 [std](https://www.luogu.com.cn/paste/2ledkyub)。 $\large{练习题}$ [P3250 [HNOI2016] 网络](https://www.luogu.com.cn/problem/P3250) * * * ### **3.11.[Noble Knight's Path](https://www.luogu.com.cn/problem/CF226E) 重剖+主席树+二分** 首先这题要保存多颗树的状态返回查询，所以考虑使用主席树。 其次，这道题要找到路径上的第 $k$ 个没有被入侵过的城堡。 发现这个查询有单调性，也就是排名单调性。 所以考虑二分，只要在对应版本的主席树上二分即可。 附上 [std](https://www.luogu.com.cn/paste/0n28vk9n)。 * * * ### **3.12.[Moonwalk challenge](https://www.luogu.com.cn/problem/CF1045J) 重剖+二分+hash** 折磨的黑，前面的练习题里面提到过了，所以我还是讲下好了。 首先讲下部分的做法，考虑直接暴力开搞。 给路径上的字符串直接整出来，然后对着 hash 开跑匹配。 很好的是，hash 要的空间是 $2.6\times 10^{11}$。而且至少得是 $long long$，而且容易被卡。 所以考虑优化。 预处理出每条重链向上和向下的 hash 值，然后像之前一样。 对于跨越重链的部分就用 $u\rightarrow lca,lca\rightarrow v$ 的方法拆分即可。 发现这个 hash 他具有可减性与单调性，所以考虑套上二分。 附上 [std](https://www.luogu.com.cn/paste/0jmkxcjl)。 $\large{练习题}$ [Misha and LCP on Tree](https://www.luogu.com.cn/problem/CF504E) hash+重剖。 [std](https://www.luogu.com.cn/paste/8aqqdbuy)。 [P6088 [JSOI2015] 字符串树](https://www.luogu.com.cn/problem/P6088) 可以 hash+重剖捏 [P9399 「DBOI」Round 1 人生如树](https://www.luogu.com.cn/problem/P9399) 重剖+hash+二分。 详情可以见[题解](https://www.luogu.com.cn/blog/Hok/solution-p9399)。 [P9997 [Ynoi2000] pmpkmp](https://www.luogu.com.cn/problem/P9997) 这题我不评价了，CF1045J 加强版。 见[题解](https://www.luogu.com.cn/blog/Hok/solution-p9997)吧。 std 不能给（题目限制），但是可以私信找我要。 * * * ### **3.13.[Tourists](https://www.luogu.com.cn/problem/CF487E) 圆方树上重剖+multiset 存信息维护** 这题挺板子的，但是属于一个典例了，所以还是拿出来讲下吧。 首先发现这题是个图，所以没法做了。 我们考虑使用广义圆方树，把图变为树。 然后再在树上使用树链剖分。 但是要注意的是，这题不能在圆点改权值时，改周围所有方点的权值，不然会被菊花图卡到 $n^2$。 所以对于一个方点，multiset 里面存它所有子节点的权值。然后修改一个圆点时，就只需要动它父亲的 multiset（它的父亲必然是一个方点）。询问时，仍然可以正常询问，只不过如果 $lca$ 是一个方点，那还要额外计算 $fa[lca]$ 的权值对答案的贡献。 这样就做完了。 std 就不附了，这题我写的太抽象了。 * * * ### **3.14.[GSS7 - Can you answer these queries VII](https://www.luogu.com.cn/problem/SP6779) 重剖+最大子段和** 这个很经典啊，但是我忘记给他拿出来了，现在补下讲解。 首先是最大子段和这个经典操作。 考虑线段树维护几个信息： * $\mathrm{ans}$ 表示这个节点的最大子段和 * $\mathrm{sl}$ 表示从左开始的最大连续子段和 * $\mathrm{sr}$ 表示从右开始的最大连续子段和 * $\mathrm{s}$ 表示这个节点维护区间的和 * $\mathrm{lz}$ 代表这个节点的懒标记的值 * $\mathrm{f}$ 代表这个节点是否有懒标记 那就很好处理了，这边我就讲下 merge 应该就够了： tree merge(tree l,tree r) { tree res;res.lz=res.f=0; res.sl=max(l.sl,r.sl+l.s);res.sr=max(r.sr,l.sr+r.s); res.s=l.s+r.s;res.l=l.l;res.r=r.r; res.ans=max(l.ans,max(r.ans,l.sr+r.sl)); return res; } 合并的时候，考虑 $$res.ans=max(l.ans,max(r.ans,l.sr+r.sl));$$ 即可。 对于树链上的查询，我们考虑把 $u\rightarrow v$，分为 $u\rightarrow lca,lca\rightarrow v$，然后拿 $resl$ 维护左边答案，$resr$ 维护右边的答案，最后合并即可。 注意，这里合并的时候要把 $resl$ 或者 $resr$ 的 $sl,sr$ 翻转一下，因为树上路径不是从 $lca$ 出发向 $u,v$ 走的，而是从 $u$ 到 $v$ 的。 附上 [std](https://www.luogu.com.cn/paste/migf2vzo)。 ------------ ### **3.15.[P3925 aaa被 续](https://www.luogu.com.cn/problem/P3925) 思路转化+重剖** 可以见我的[题解](https://www.luogu.com.cn/blog/Hok/solution-p3925)喵，代码见题解了。 对了，吐槽一句，这个题目的名称他是敏感词，这点我真的没绷住。 首先是简要题意： > - 每个点都有一个权值。 > - 对于每个点，把他的子树中的所有点的权值从小到大排序，记答案为权值大小乘以排名。 > - 询问每个点的答案的和。 如果没有看的很懂的话，可以看题目解释这张图：  然后我们来考虑下怎么做。 首先考虑暴力，给每颗子树都弄个堆暴力计算，这样的复杂度是 $O(n^2\log n)$，直接原地升天。 接着考虑如何优化。 首先，从数据范围上分析，$n\le 5\times 10^5$ 这种数据，大概是 $O(n\log n)$ 或者小常 $O(n\log^2 n)$。 所以由此我们得到对于正解而言每个点应该只需要计算一次即可。 那么会想到什么？ 拆分。 因为每个点都被反复计算了很多次，所以我们可以把这么多次拆出来，化为一次考虑，那就可以成功降低复杂度。 接着考虑如何拆分。 我们考虑一个抽象概念：对于点 $i$，有一个有着 $si_i$ 容量的序列（这里 $si_i$ 的意思是 $i$ 的子树大小），然后排在第 $j$ 位上的排名是 $si_i-j+1$，那么我们把一个权值为 $w$ 的点填进第 $j$ 位的时候，对答案产生的贡献即为 $(si_i-j+1)\times w$。 而对于点 $u$ 而言，就要把他填入 $1\rightarrow u$ 的路径上的每个点的序列中。 那么我们要最大化答案，显然有一种贪心的想法，就是优先把权值最大的点填进去，这样的话乘数最大，最优。 （这里如果不是太理解的话可以手模下样例，样例是按照 $3,2,5,4,1$ 的顺序计算。） 然后呢，每个点都开一个这样的序列空间显然会炸。 这个时候发现了什么呢？ 我们每次填的时候，需要的只是目前这个位置的排名值而已，而且我们移动这个序列也是连续的。 也就是，我们对于点 $i$ 的序列，就可以把他排名值初始设定为 $si_i$，填一个空，排名值就 $-1$。 相当于使用一个变量完成了点 $i$ 的排名值的维护。 那么我们可以考虑把这个排名值直接作为这个点的一种权值。 因为我们操作点 $u$ 的时候，要把他填入 $1\rightarrow u$ 的路径上的每个点的序列中。 结合下上面对于答案的贡献的计算式，我们可以把上面式子中的 $w$ 提取出来。 接着申明一些定义： - $a_i$ 代表 $i$ 这个点目前的排名值。 - $w_u$ 代表 $u$ 这个点的权值。 - $\sum_{a_i}^1$ 代表的是 $u$ 到 $1$ 的路径上所有点的排名值之和。 那么对答案的贡献式即为 $\sum_{a_i}^1\times w_u$。 贡献式成功推出来了，那只要快速算 $\sum_{a_i}^1$ 即可。 因为这是个树上连续路径的排名值和，所以考虑重链剖分+线段树维护。 然后因为序列上的点的位置已经被填了，所以要把路径上所有点的排名值 $-1$，也用重链剖分维护即可。 那最后归纳一下操作即为： > - 先把点 $i$ 的值赋为 $si_i$。 > - 然后根据题目给出的权值大小，从大到小执行操作。 > - 对于点 $u$，用线段树求出 $1\rightarrow u$ 的路径上的点值和。 > - 然后把求出来的这个值乘上点 $u$ 的权值，累加到 $ans$ 中。 > - 然后把 $1\rightarrow u$ 的路径上的点值都 $-1$。 > - 最后输出 $ans$ 即可。 $\large{更新(24.2.2)}$ 原本我以为，我写完这个冷门树剖题的题解就不会再与这题相见了。 结果就在今天上午的模拟赛里的 G 题就和这题基本没有区别。 只是从求最大价值变为了最小价值，并且询问每个点对总答案的贡献。 很快啊，我就开始想树剖做法了。 然后发现树剖他是通过离线合并了统计答案的过程来做的，所以无法完成每个点的询问。 这下就给我气到了，出了个原题可用树剖的题还把我最喜欢的树剖做法卡了。 于是脑子就被我扔掉了，我们考虑使用启发式合并平衡树来解决这个问题。 怎么启发式呢，考虑用重链剖分来启发式合并，因为重儿子有着子树大小至少为一半的特性。 所以我们的复杂度是有保证的，为 $O(n\log^2n)$。 这下就做完了，实现稍微有点难度，可以见代码。 这里给出的代码是我赛场的时候写的，赛场那题是多测，先读点权再读边的。 这里的傻逼作者没写 FHQ 的原因是因为不会，学过 Splay 的原因是因为学了 LCT。 $\large{后记}$ 虽然赛场上我是给这题写出来了，但是因为做法巨复杂，所以喜提最抽象解。 听讲课的时候我才发现，原来 G 题他有个题目条件保证为二叉树，所以可以直接上树状数组，而且正常还可以用线段树合并。 还有个傻逼赛场上写的时候没有清空重儿子数组一直 TLE 0，卡了半小时，我不说是谁啊。 ------------ ### **3.16.[Tree or not Tree](https://www.luogu.com.cn/problem/CF117E) 基环树+重剖** 也可以见 [题解](https://www.luogu.com.cn/blog/Hok/solution-cf117e) 捏。 首先我们考虑下题目中的基环树要是变成树该怎么处理。 用每个线段树维护重链上的 $1$ 边数量 $cnt$。 如果取反就直接把数量改为长度 $r-l+1$ 减掉原来的数量 $cnt$ 即可。 考虑翻转时存在两种情况： 1. 将 $0$ 改为 $1$ 时，$1$ 边连接的极大连通块数量会 $-1$。 2. 将 $1$ 边改成 $0$ 边时，极大连通块数量会 $+1$。 那么让初始答案为 $n$，每次操作在线段树修改时顺带统计一下 $1$ 边变化量以更新答案就好了。 那面对基环树呢？ 考虑转化为树，把环缩点之后就成了一颗树。 缩点很简单，直接拓扑排序打标记即可。 剩下的环上的点考虑再开一颗线段树维护，就可以顺利完成此题了。 附 [std](https://www.luogu.com.cn/paste/gqyzbx11)。（因为没用 namespace 封装也没用 struct 封装所以很臃肿。） $\large{练习题}$ [P4949 最短距离](https://www.luogu.com.cn/problem/P4949) 更简单一点，无需缩点，这题考察的是树和基环树间的联系。 ------------ ### **3.17.[P9808 [POI2022~2023R1] zbo](https://www.luogu.com.cn/problem/P9808) 推式子转化+重剖** 这边我就转载下题解吧，也可以去[题解文章](https://www.luogu.com.cn/blog/Hok/solution-p9808)那里看捏。 美妙树剖，比较套路了吧，反正一眼秒了。 原本不想补题解的，但是做到这题还是我的**御用纯情娇羞可爱内向小男娘** Loser_Syx 把这题推给我了捏。 题目这么大个式子摆在眼前肯定先考虑~~暴力~~化简下啊。 题目给定的一个函数外面再套求和肯定是不太好做的，所以考虑先拆里面。 里面的直接使用树上距离公式就行了（注意这里的深度是指到根节点的距离）。 $$dis(x,y)=dep_x+dep_y-2\times dep_{LCA(x,y)}$$ 用这个式子就可以把之前那个又臭又长的式子破开成为： $$\sum\limits_{i=1}^k\sum\limits_{j=1}^k dep_{a_i}+dep_{a_j}-2\times dep_{LCA(a_i,a_j)}$$ 然后把这里面好算的东西拿出来破开： $$2\times(k-1)\times \sum\limits_{i=1}^kdep_{a_i}-4\times\sum\limits_{i=1}^k\sum\limits_{j=i+1}^kdep_{LCA(a_i,a_j)}$$ （虽然我感觉很惊讶，但是另一篇题解后面的这个系数好像写错了，应该是 $4$，原因是把从 $1$ 开始变为从 $i+1$ 开始应该再乘上一个 $2$ 的系数。） 然后把前面一坨和后面那一坨分开，也就是令 $ans1=\sum\limits_{i=1}^kdep_{a_i},ans2=\sum\limits_{i=1}^k\sum\limits_{j=i+1}^kdep_{LCA(a_i,a_j)}$。 然后前面那玩意很好维护了，出新点的时候直接加上这个点即可。 重点则在后面这一块怎么求。 首先思考下这一坨他在树上的意义是什么？ 是根到他们 LCA 的距离吗？（那不是说了和说了一样。） 所以考虑为什么我们可以把 $dis(x,y)$ 拆开的原因。 那他的意义即为：$1\rightarrow a_i,1\rightarrow a_j$ 路径相交的长度。 路径相交？那我们便可以在把一个村庄 $i$ 变为新的城堡后把 $1\rightarrow i$ 上的路径的边权全部倍数 $+1$。 查询的时候只要直接询问 $1\rightarrow i$ 上的路径长度求出来加入 $ans2$ 中即可。 具体细节见又臭又长的代码了。 附上 [std](https://www.luogu.com.cn/paste/jl66r9ba)。 $\large{练习题}$ 这里都是一些美妙推式子喵。 [P4211 [LNOI2014] LCA](https://www.luogu.com.cn/problem/P4211)，这题典中典了，不多介绍了。 附 [std](https://www.luogu.com.cn/paste/3fn1nk6v)。 [P5305 [GXOI/GZOI2019] 旧词](https://www.luogu.com.cn/problem/P5305)，这题就是上一题的简单推广。 附 [std](https://www.luogu.com.cn/paste/2vswb1b9)。 [P5559 失昼城的守星使](https://www.luogu.com.cn/problem/P5559) 这个题和 LCA 那题差不多吧，以这个为基础大力推就完了。 详细的 solution 可以看我的 [题解](https://www.luogu.com.cn/blog/Hok/solution-p5559) 喵。 [Arkady and a Nobody-men](https://www.luogu.com.cn/problem/CF860E) 和板子题 LCA 差不多，但是要卡常，可以当做练手题，没过的话全加 inline 就行了。 std 在[题解](https://www.luogu.com.cn/blog/Hok/solution-cf860e)里了。 -------------- ### **3.18.[P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719) ddp** 经典中的经典，ddp 板子。 因为考试正常都更喜欢**思维型**的题目，所以如果出到树剖的话，更大的可能是出 ddp，所以**非常重要**。 换句话说，如果学了树剖没学 ddp，就基本等于白学了。 首先，考虑把题目中的修改操作去掉，那么，这题就变成了一个非常板子的**树形 dp**。 考虑下这个 dp 的式子，先设计状态：$\mathrm{f_{i,0/1}}$ 表示**选/不选**第 $i$ 的点的**最大权独立集**。 那么转移方程式就是： $$f_{i,0}=\sum\limits_{fa[j]=i}\max(f_{j,0},f_{j.1})$$ $$f_{i,1}=\sum\limits_{fa[j]=i}\max(f_{j,0})+a_i$$ 最后的答案就是 $\max(f_{i,0},f_{i,1})$。 接着我们来考虑下修改。 因为当前这个点的答案是和他的儿子有关的，所以当我们修改了 $x$ 这个点的点权的时候，就要修改 $1\rightarrow x$ 上的所有点的 $f$ 值。 这样的复杂度是 $\operatorname{O(n^2)}$，显然无法通过此题。 这个时候，我们先考虑一手期望复杂度，应该为 $\operatorname{O}(n\log^2n)$。 经典 $\log^2n$，合理推测一手应该使用重剖，因为重剖可以把一颗树划分为 $\log n$ 条重链，只要能实现链间转移 $\operatorname{O}(1)$ 即可顺利完成问题。 考虑下重剖的重点在哪里？ 肯定是**重**字。 考虑再设计一个状态：$\mathrm{g_{i,0/1}}$ 表示 $i$ 点的**所有轻儿子的最大权独立集/所有轻儿子都 不 选的最大权独立集**。 这样的话就可以把 $\sum$ 去掉了，状态转移方程式即为： $$f_{i,0}=g_{i,0}+\max(f_{son_i,0},f_{son_i.1})$$ $$f_{i,1}=g_{i,1}+f_{son_i,0}+a_i$$ 这个时候我们发现，虽然 $\sum$ 没了，但是 $f_{i,1}$ 的方程中还有一个顽固的 $a_i$。 所以我们直接考虑把 $a_i$ 合并进 $g_{i,1}$ 中，详细的定义即为：$\mathrm{g_{i,1}}$ 表示 $i$ 点的**所有轻儿子都 不 选且选 $i$ 点的最大权独立集**。 这个时候第二个式子也就变成了： $$f_{i,1}=g_{i,1}+f_{son_i,0}$$ 接下来的问题就是如何快速维护 $f_{i,0/1},g_{i,0/1}$ 了。 思索一下学过的优化 dp 的各种方式，有 DS 优化，矩阵优化，斜率优化等等。 首先排除斜率优化的可能性，仔细思索一二会发现 DS 也不好优化，所以这里考虑能否使用**矩阵优化**。 矩阵优化的核心所在，便是使用转移矩阵与矩阵乘法，利用快速幂使复杂度从 $n$ 变为 $\log n$。 但是我们这个式子里又是 $\max$ 又是 $+$ 的，怎么化为矩阵呢？ 不难发现，$\max$ 是不能转化为 $+$ 的，但是 $+$ 可以转化为 $\max$。 所以我们考虑先把式子转化为一个大 $\max$ 的形式，即为： $$f_{i,0}=\max(g_{i,0}+f_{son_i,0},g_{i,0}+f_{son_i.1})$$ $$f_{i,1}=\max(g_{i,1}+f_{son_i,0},-\infty)$$ 这样的话转移方程里就只剩下 $\max$ 了。 但是矩阵乘法明明是乘法，哪来的 $\max$ 和 $+$ 呢？ 这个时候就要使用**广义矩阵乘法**了。 为了满足结合律，并且用上 $\max$ 和 $+$，其计算方式即为： $$res_{i,j}=\max\limits_{k<=n}(a_{i,k}+b_{k,j})$$ 这样定义的**广义矩阵乘法**是满足结合律的，笔者不会证但是可以感性理解一下，$\max$ 和 $+$ 都是满足结合律的，所以将这两者结合时也是满足结合律的。 $$\begin{bmatrix}f_{son_i,0}&f_{son_i,1}\\\end{bmatrix}\cdot\begin{bmatrix}g_{i,0}&g_{i,1}\\g_{i,0}&-\infty\\\end{bmatrix}=\begin{bmatrix}f_{i,0}&f_{i,1}\\\end{bmatrix}$$ 这里右边的那个矩阵推出来的方法就与正常矩阵乘法题目的推法类似，这里不再赘述。 但是这里有个坑点，因为转移矩阵存在 $i$ 上，而前面的那个矩阵是存在 $son_i$ 上的，这样的乘法顺序是有问题的，需要调转一下顺序，即为： $$\begin{bmatrix}g_{i,0}&g_{i,0}\\g_{i,1}&-\infty\\\end{bmatrix}\cdot\begin{bmatrix}f_{son_i,0}\\f_{son_i,1}\\\end{bmatrix}=\begin{bmatrix}f_{i,0}\\f_{i,1}\\\end{bmatrix}$$ 接着对于每次修改点权，只需要修改 $g_{i,1}$，一路向上跳修改 $f_{i,0},f_{i,1}$ 即可。 附 [std](https://www.luogu.com.cn/paste/gaugz3em)。 **P.S.:这里把广义矩阵乘法部分循环展开了，速度快亿点。** $\large{练习题}$ [P4751 【模板】"动态DP"&动态树分治（加强版）](https://www.luogu.com.cn/problem/P4751) 这题，号称卡了树剖，但是我们还是可以莽过去，重点优化即为以下三点： 1. fread 快读。 2. 循环展开广义矩阵乘法。 3. 减少函数调用。 第一点和第二点都十分简单，重点在于第三点。 不难发现，我们函数中有个叫 $query$ 的函数，用来查询线段树上一段区间的值。 但是仔细观察下我们查询的区间，这些区间都正好对应线段树上的一个点。 所以我们根本没有必要写这个 $query$ 函数，只要记下**每个点要查询的区间对应的线段树上的点**即可，查询时直接返回线段树上这个点的值就行了。 附上 [std](https://www.luogu.com.cn/paste/k1ffihfe)。 [P5391 [Cnoi2019] 青染之心](https://www.luogu.com.cn/problem/P5391) 这题不是 ddp，但是树上背包还是很有意思的。 本题的难度就在于如何看出来是个树的问题，看出来后就可以轻松秒杀了。 附 [std](https://www.luogu.com.cn/paste/o10dbku9)。 [P5024 [NOIP2018 提高组] 保卫王国](https://www.luogu.com.cn/problem/P5024) 这题有非 ddp 的倍增做法，但是从练习 ddp 的角度来说还是写 ddp 好了。 采取第一篇题解中的算法一，对着模板的矩阵进行修改。 首先因为我们要求的值需要取 $\min$，所以广义矩阵乘法的地方要修改为 $\min$。 其次因为要取 $\min$，所以初始值全部赋为 $\infty$。 同时修改矩阵转移式为： $$\begin{bmatrix}\infty&g_{x,0}\\g_{x,1}&g_{x,1}\end{bmatrix}*\begin{bmatrix}f_{son_i,0}\\f_{son_i,1}\end{bmatrix}=\begin{bmatrix}f_{x,0}\\f_{x,1}\end{bmatrix}$$ 对于必选和必不选的问题，只需要修改为 $\infty,-\infty$ 即可。 P.S.:有个消愁因为把 dfn 写成了 id 导致 $48$ 分，警钟撅烂。 附 [std](https://www.luogu.com.cn/paste/onc6k1pm)。 ------------------------ ### **3.19.[瓦里奥世界 Rujia Liu loves Wario Land!](https://www.luogu.com.cn/problem/UVA11998) 启发式合并树剖** 吐槽一句，这题能算是板子题吗，感觉这种套路应该是能算板子的，但是我只做过这一道启发式合并树剖。 简要题意： > - 给定 $n$ 个点的森林，每个点都有权值，有三种操作，总共 $m$ 个操作和模数 $k$。 > - 1. 给定点 $u,v$，给点 $u,v$ 间连一条边，若已连通则忽略。 > - 2. 给定点 $x$ 和值 $val$，表示把点 $x$ 的权值改为 $val$。 > - 3. 给定点 $u,v$ 和值 $w$，查询 $u\rightarrow v$ 的路径上点权小于等于 $w$ 的点个数，以及点权小于等于 $w$ 的点的点权乘积对 $k$ 取模。如果不存在这样的点则只输出一个 $0$。 > - $n\le5\times10^4,m\le10^5,k\le33333$，多测，强制在线。 抓住题面重点，虽然好像都挺难办，但最优特色的还是强制动态连边。 一个树上路径查询问题，首先想到**重剖和动态树**。 强制动态连边，考虑使用**动态树**如：LCT 解决。 接着来观察下查询操作，是给定一个值根据这个值比大小查询。 一眼 LCT 不可做的样子。~~至少我不会~~。 那么只能来尝试重剖了，但是重剖必须要树的形态固定才能剖，貌似很难解决。 接着发现没有动态删边，可以考虑使用启发式合并的方法来每次暴力重构，把小树的答案接到大树中。 那么到现在主体思路已经确定下来了，即为**启发式合并重剖**。 接着来考虑怎么维护这个题目中要的信息。 $3$ 操作的查询极为复杂，又是小于等于 $k$ 的数量，又要乘积，感觉线段树根本就不可做。 既然 polylog 做法死掉了，考虑下万能的暴力数据结构：**分块**。 分块，重点考虑如何快速跳掉一个块。 考虑把块里的数按权值排序，再做一个前缀积，就可以在上面二分最后一个小于等于 $k$ 的位置累加贡献了。 到这里整体的思路就出来的差不多了，接下来是一些实现上的问题。 主要是有关于**启发式合并重剖**的，合并后新树仍要保证重剖的性质。 设新树的根为 $rt$，连边的两个点为 $x,y$ 且 $fa_y=x$。 那么我们要修改的就是 $rt\rightarrow x$。 在这上面的点，他们的子树大小都增加了 $si_y$。 考虑怎么维护这个 $si_y$。 还是寻求于万能的分块，散块暴力改，整块打标记即可。 若 $si_y>si_{son_x}$，则替换 $son_x$ 为 $y$。 而 $x\rightarrow rt$ 部分不需要更改。 因为这一部分在合并前，本身的复杂度是对的，所以合并后复杂度仍然是对的，没有必要追求严格的重剖性质。 那这样就保证了 $rt$ 出发到树中的任意一个点最多只会经过 $\log(si_{rt})$ 条轻边。 复杂度问题解决了，最后来总结下整体的做法。 1. $1$ 操作，先启发式合并，接着判断是否需要换重儿子，如果要换重儿子就暴力重构。 暴力重构合并进来的子树信息，并且用分块修改子树大小。 2. $2$ 操作，直接找到对应的值删除并放入新值重构分块即可。 3. $3$ 操作，分为两个部分： - 先把整段的重链能跳的跳掉，并且用分块计算跳掉的点 $x$ 到重链链顶 $top_x$ 的贡献。 - 接着分块跳把还在下面的那个点往上移。 - 最后最朴素的把这个点移上来，暴力统计答案。 4. 多测一定要记得清空，可以把清空写在重剖第一遍 dfs 里。 代码可以见[题解](https://www.luogu.com.cn/article/y95xveoc)。 -------------------- ### **3.20.[P7671 [GDOI2016] 疯狂动物城](https://www.luogu.com.cn/problem/P7671) 推式子+维护进阶版** 可以见[题解](https://www.luogu.com.cn/article/5jkxou8q)喵。 前置知识：[P4211 [LNOI2014] LCA](https://www.luogu.com.cn/problem/P4211)。 ~~有个傻逼式子抄错了半天没推出来我不说是谁。~~ 首先说下题意中我理解错的地方，**能量石在生产之后是不会消耗的，能一直解救动物**。 所以这种题写前最好看下形式化题意对下题意理解是否有问题。 其他部分暂且不考虑，先看题目中又臭又长的那串式子： $$\sum\limits_{i \in x\rightarrow y}\!{a_i}\times\dfrac{\operatorname{dis}(i,y)(\operatorname{dis}(i,y)+1)}{2}$$ 在这里，我们发现了一个很熟悉的部分，$\operatorname{dis}(i,y)$。 像这样的树上两点距离，肯定是要无脑的给他拆成 $dep_i+dep_y-2\times dep_{\operatorname{LCA}(i,y)}$。 然后把这部分拆开看看，再把 $\dfrac{1}{2}$ 提到前面去，就得到了： $$\dfrac{1}{2}\sum\limits_{i \in x\rightarrow y}\!{a_i}\times(dep_i+dep_y-2\times dep_{\operatorname{LCA}(i,y)})(dep_i+dep_y-2dep_{\operatorname{LCA}(i,y)}+1)$$ 欸，这式子怎么越化越复杂了，难道要全部拆开吗？ 显然不是的，我们发现这里的 $\operatorname{dis}(i,y)$ 有一个与其他推式子题不一样的特性，就是其中的 $y$ 点是已经给定的。 又因为 $i$ 是 $x\rightarrow y$ 路径上的点，所以当 $i$ 是 $\operatorname{LCA}(x,y)\rightarrow x$ 的那一段时，$\operatorname{LCA}(i,y)$ 就是 $\operatorname{LCA}(x,y)$。 同理的考虑当 $i$ 是 $\operatorname{LCA}(x,y)\rightarrow y$ 的那一段时，$\operatorname{LCA}(i,y)$ 就是 $i$。 这下式子就有着美妙的性质了，再考虑下按照这两个部分给他化开。 下面式子中用 $lca$ 表示 $\operatorname{LCA}(x,y)$。 1. 当 $i\in lca\rightarrow x$ 时，式子即为： $$\dfrac{1}{2}\sum\limits_{i\in lca\rightarrow x}\!{a_i}\times(dep_i+dep_y-2dep_{lca})(dep_i+dep_y-2dep_{lca}+1)$$ 观察到 $dep_y-2\times dep_{lca}$ 是个定值，直接用 $s_1$ 来表示他，就得到了： $$\dfrac{1}{2}\sum\limits_{i\in lca\rightarrow x}\!{a_i}\times(dep_i+s_1)(dep_i+s_1+1)$$ 再接一步大力展开： $$\dfrac{1}{2}\sum\limits_{i\in lca\rightarrow x}\!{a_i}\times((dep_i+s_1)^2+(dep_i+s_1))$$ $$\dfrac{1}{2}\sum\limits_{i\in lca\rightarrow x}\!{a_i}\times(dep_i^2+2s_1dep_i+s_1^2+dep_i+s_1)$$ 最后把求和也给展开，就得到了： $$\dfrac{1}{2}\left[\sum\limits_{i\in lca\rightarrow x}{a_idep_i^2}+\sum\limits_{i\in lca\rightarrow x}{a_idep_i\left(2s_1+1\right)}+\sum\limits_{i\in lca\rightarrow x}{a_i\left(s_1^2+s_1\right)}\right]$$ 2. 当 $i\in lca\rightarrow y$ 时，式子即为： $$\dfrac{1}{2}\sum\limits_{i\in lca\rightarrow y}\!{a_i}\times(dep_i+dep_y-2dep_i)(dep_i+dep_y-2dep_i+1)$$ $$\dfrac{1}{2}\sum\limits_{i\in lca\rightarrow y}\!{a_i}\times(dep_y-dep_i)(dep_y-dep_i+1)$$ 发现其中的 $dep_y$ 为不变量，用 $s_2$ 代入展开得： $$\dfrac{1}{2}\sum\limits_{i\in lca\rightarrow y}\!{a_i}\times(s_2^2-2dep_is_2+dep_i^2+s_2-dep_i)$$ 最后再展开下求和就得到了： $$\dfrac{1}{2}\left[\sum\limits_{i\in lca\rightarrow y}{a_idep_i^2}-\sum\limits_{i\in lca\rightarrow y}{a_idep_i\left(2s_2+1\right)}+\sum\limits_{i\in lca\rightarrow y}{a_i\left(s_2^2+s_2\right)}\right]$$ 至此，最艰难的一步就完成了。 然后再去看题面中其他的部分，因为有版本回溯，所以直接大力上一颗主席树。 对于链加，直接标记永久化即可。 主席树上维护三个值，分别是正常的点权和，乘上 $dep$ 的点权合和乘上 $dep^2$ 的点权和。 接着大力维护即可，详情见代码了，有关变量部分有些许解释。 代码就见[题解](https://www.luogu.com.cn/article/5jkxou8q)了。 ------------------- ### **3.21 [P9620 歌姬](https://www.luogu.com.cn/problem/P9620) 树剖魔改 dfn 序** 可以见[题解](https://www.luogu.com.cn/article/ds4wrz82)喵。 简要题意： > 给定有 $n$ 个点的树，最开始所有点都是白点，每次操作给一个点染黑/染白。 > > 操作后，得到所有黑点的导出子树，求使这个导出子树的根的深度变化最少要删掉多少黑点。 > > 特别的，如果删空了也算变化。 如果只求根节点的话显然是一个一眼题。 这个比较简单就不再赘述，直接给出经典结论： - 对于点 $a_{1,2,\dots,n}$，他们的 LCA 即为 dfn 序最小和最大的点的 LCA。 原因也比较显然，有兴趣的读者可以自证。 接着考虑怎么样改变根节点的同时删掉的点最少。 我们考虑其实只有两种可能： 1. 根节点 $x$ 处分多叉子树，每叉里都有黑点。 此时我们考虑只保留一叉子树然后把多余的全删了就行了。 也就是找到总点数 $w$，含有黑点数最多的子树黑点数 $w'$，答案即为 $w-w'$。 2. 根节点处后只有一叉子树，但是根节点是黑点。 其实这类情况可以直接合并进 $1$ 里，我们把根节点这个黑点当做是子树外的另一叉即可。 这下就变成了，单点修改权值，查询给定点 $x$ 的儿子的子树最大权值。 如果遍历儿子算子树和这显然复杂度会爆掉，所以我们不要写成单点加，子树查。 把这个转化一下，变成链加，单点查。 也就是对于点 $x$，我们给 $x\rightarrow 1$ 的路径加上修改的权值，那么查询的时候点 $y$ 对应的权值就是他的子树权值和了。 接着我们要考虑的就是快速查询所有儿子权值最大值的方法。 考虑把这东西也交给线段树维护，但是问题来了： - 对于一个点 $x$，他的所有儿子的 dfn 序不是连续的，这怎么办。 注意到我们不需要子树 dfn 序连续的性质，只需要保证重链 dfn 序连续即可。 所以我们可以对树剖的第二遍 dfs 略加修改，让轻儿子的 dfn 序也连续。 然后就可以比较方便的实现了，具体代码可以看[题解](https://www.luogu.com.cn/article/ds4wrz82)喵。 ----------------------- ### **3.22.[MEX Tree Manipulation](https://www.luogu.com.cn/problem/CF1740H)** ddp 思想+找性质 可以见[题解](https://www.luogu.com.cn/article/fmaflusn)喵。 注意下权值是**儿子**权值的 MEX ，那感性理解的感觉来说，感觉答案不会很大。 不妨设权值达到 $i$ 至少需要 $f_i$ 个点。 那么我们可以得到递推式 $f_j=\sum\limits_{i=0}^{j-1}f_i +1$，以及初始条件 $f_0=1$。 然后你就会发现其实 $f_i=2^i$，所以一个点的权值最大也就会取到 $\lfloor\log n\rfloor$。 也就是值域只有 $\log n$ 这个性质，或许会很有用？先记下来。 然后看题，动态加叶子。 那这也就意味着修改本质上就是 $1\rightarrow i$ 的一个路径修改，然后对于每个 $i$ 改过去。 为了平衡复杂度，我们就要做到快速的跳的过程。 树上，修改，带值，首先想到 ddp。 借助 ddp 的思想，我们可以做到每次修改只有 $O(\log n)$ 次跳跃。 然后要考虑的就是如何快速修改一条重链，也就是快速修改重儿子了。 因为答案是全局的和，所以我们可以用差分的方法，先去掉修改的链的答案，然后再加上新的答案来解决。 注意到 $\log n$ 的这个权值大小，可以支持我们把儿子中是否有权值 $i$ 压为压成一个 `int`。 设这个值为 $x$，当前位的权值就是 `lowbit(x)`。 为了快速搞出重链的修改，我们先处理出轻儿子的权值压成一个 `int`，那么权值的查询就变成了或上重儿子的权值再取 `lowbit`。 然后很显然的发现了重链的这个信息其实就是函数一层一层套在一起。 我们考虑用线段树来维护这个复合函数的值。 那这个复合函数必然要由一些美妙的性质。 然后我们就注意到了，对于这个函数本身只会有两种取值。 也就是原本的集合的 MEX 和插入 MEX 后得出的新的 MEX'。 因为我们只插入一个数，所以通过函数运算之后也只会有这两种取值。 接着我们要处理的就是这个复合函数套了很多层的情况如何快速合并。 对于两个复合函数，设左边为 $x$ 右边为 $y$。 左边的 MEX 为 $w1$，插入 MEX 后的值为 $w2$，同理设右边的 MEX 为 $w3$，插入 MEX 后的值为 $w4$。 那么如果 $w3=w1$，则插入右边的 MEX 左边就会得到 $w1$，否则就是得到 $w2$。 同理如果 $w4=w2$，则插入右边的 MEX 左边就会得到 $w2$，否则就是得到 $w1$。 这样我们就完成了复合函数的合并。 考虑直接把这东西扔到线段树上去维护，那也就是线段树节点的 merge。 因为 $w1,w2$ 表示的都是最上面那个点算出来最后的值，而判断条件是最下面的那个点的 MEX，所以这里用于条件的 MEX 还要独立记录下来。 再加上这题要查询和，所以我们还要额外维护一个 $s1,s2$ 表示插入/不插入 MEX 的值。 最后因为对于每一条重链，我们都要从最底下那个重儿子开始一路向上合并才能得到正确的值，所以对于链顶我们再记录一个链底，查询的时候从链顶查询到链底就行了。 注意下 merge 的顺序即可轻松实现。 感觉唯一的难点就在于发现复合函数的取值只有两种了。 代码实现可能稍微会有点问题，比起正常的树剖略有不同，详细代码可以见[题解](https://www.luogu.com.cn/article/fmaflusn)喵。 * * * 终于写完了，难受的。 （其实还有很多的模板，只不过我还没写所以随缘更新了。） 接下去的练习就要来到我的折磨题单里了/cf。 [『应用（折磨）篇』重链剖分](https://www.luogu.com.cn/training/440258) 共 $98$ 道紫黑！。 * * * ## **3.23.后记** 这里说说我自己写了这么多重剖题后的感受吧。 首先是有关于出锅的方面：感觉每道题都**五彩斑斓**的，但出锅最多的总是**剖**。 比如我个人而言，就写过随机剖分，$si_v+=si_u$ 这种逆天东西。 然后是有关于重剖的用途，重剖其实是可以把一些序列上的问题强制放到树上的。 但是实际上我认为的好树剖题都有一个崭新的部分，比如 [P3925 aaa被 续](https://www.luogu.com.cn/problem/P3925) 就挺好的。 还有 [P7735 [NOI2021] 轻重边](https://www.luogu.com.cn/problem/P7735) 这样的好题。 个人感觉，这种题，才是重剖存在的意义吧，而不是单纯把操作搬上树的恶心题。 虽然说重剖真的不是很常考了，但是既然都已经看到这篇文章，学到这了，那就练完吧！ 对了，后面的 LCT 真的可以别学，真的不太用的到。 * * * # 4. **长链剖分** 讲长剖前先丢上[长剖模板题](https://www.luogu.com.cn/problem/P5903)吧。 对于树链剖分而言，长剖和树剖可以说是比较相近。（隔壁那个实剖不一样一点。） 所以我们考虑使用与重剖相近的方法讲长剖。 * * * ## 4.1. 定义 * 定义 **长儿子** 表示其子节点中子树深度最深的子节点。如果有多个子树深度最深的子结点，取其一。如果没有子节点，就无长儿子。 * 从这个结点到长子节点的边为 **实边**。 * 到其他子节点的边为 **虚边**。 * 若干条首尾衔接的实边构成 **长链**。 * 把落单的结点也当作长链，那么整棵树就被剖分成若干条长链。 * 对于一条长链 * 定义链底为这条链深度最大的节点 * 定义链顶为这条链深度最小的节点 附图（真的不想手画所以拿了一张树剖姐姐的）：  其中绿色边为实边，蓝色边为虚边。 * * * ## 4.2. 实现 根据上面的定义，我们可以得到长剖的预处理 dfs 代码。 **P.S.：注意链顶链底的定义** void dfs1(int x,int f) { dep[x]=dep[f]+1;fa[x][0]=f;h[x]=-1; for(int i=1;i<20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=0;i<g[x].size();i++) { dfs1(g[x][i],x); if(h[g[x][i]]>h[x]) son[x]=g[x][i],h[x]=h[g[x][i]]; } h[x]++;if(!h[x]) h[x]=1; } void dfs2(int x,int top) { dn[top].push_back(x);tp[x]=top; if(g[x].empty()) return; dfs2(son[x],top); for(int i=0;i<g[x].size();i++) if(g[x][i]!=son[x]) { up[g[x][i]].push_back(g[x][i]); for(int j=1;j<=h[g[x][i]];j++) up[g[x][i]].push_back(fa[up[g[x][i]].back()][0]); dfs2(g[x][i],g[x][i]); } } * * * ## 4.3. 应用（板子） 例题：[P5903 【模板】树上 K 级祖先](https://www.luogu.com.cn/problem/P5903)。 倍增出每个节点向上 $2^p$ 个节点的父亲，对于每次查询的 $k$，我们先把 $x$ 跳到 $k$ 第一个二进制位代表的数的位置，这样就可以把剩下的距离缩减到 $\lfloor \frac{k}{2} \rfloor$ 以下，这样，当前这个节点的链长肯定比剩下要跳的长度更大了，所以直接向上跳即可。 更清楚的描述见图（[来源](https://www.luogu.com.cn/blog/b6e0/solution-P5903)）：  附上 [std](https://www.luogu.com.cn/paste/qxl4lxh8)。 **P.S.：这里注意不要全开 long long，但记得给快读快输里开 long long！！！（不信看我提交记录）** * * * ## 4.4. 应用（长剖优化 dp） 例题：[Dominant Indices](https://www.luogu.com.cn/problem/CF1009F)。 题意已经很清楚了，这里不再过多阐述。 首先考虑朴素 dp:状态设计：$dp_{u,dep}$ 表示 u 的子树中与 u 距离为 dep 的点的个数。转移方程如下: $$dp_{u,dep}=\sum_{v \in son_u} dp_{v,dep-1}$$ 显然这个时空复杂度是 $O(n^2)$ 的。 再看眼数据范围，好，真就再看一眼就会爆炸：$n\le 10^6$。 所以来考虑优化吧。 结合一下我们的标题，考虑下用长剖优化。 我们会发现，长剖中的长链有着非常美妙的性质，就是长儿子肯定是当前子树最长的那条链上的。（这不是废话吗，但是就是这个美妙性质。） 对于一个节点 $u$，我们先对它的长儿子做 dp，让长儿子把 dp 出来的东西直接存到 $dp_u$ 里面去（当然观察 dp 式可以发现这边需要错一位）。 其他的儿子直接暴力合并上去就好了。 显然每条长链最多被合并一次，所以就得到了美妙的 $O(n)$ 复杂度。 再采取指针写法弄下 dp 数组，就可以得到时空复杂度 $O(n)$ 的美妙 dp 了。 附代码 [std](https://www.luogu.com.cn/paste/yqo6jmlm)。 $\LARGE{练习题}$ [P3899 [湖南集训] 更为厉害](https://www.luogu.com.cn/problem/P3899) * * * ## 4.5. 后记（个人关于长剖看法） 长剖好像都只剩下神仙题了。 更多练习题可以见[题单](https://www.luogu.com.cn/training/470239)了。 后续应该会再补一些例题，但是貌似实用性不大？ * * * # 5. **平衡树部分（Splay）** 大家可能会好奇为什么突然在树剖中插入一个平衡树的章节。 别问，问就是后面的实链剖分，也就是 LCT 他里面要用（其实可以写 FHQ 的，但是有点麻烦）。 所以不学也得学 Spaly 喽！（Splay and play S/cf） （这里的平衡指的是非严格平衡捏。） * * * ## 5.1. 二叉搜索树 在学习平衡树前，我们要先学习一个东西叫做二叉搜索树。 先给出定义。 ### 5.1.1. 定义 1. 空树是二叉搜索树。 2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。 3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。 4. 二叉搜索树的左右子树均为二叉搜索树。 由此我们可以得到二叉搜索树的性质，就是:$$w_{ls}<w_{rt}<w_{rs}$$ $ls，rt，rs$ 的意思分别是左儿子，根，右儿子。 $w$ 数组是指点权。 所以由此我们可以得到第二个性质，二叉搜索树的中序遍历可以得到一个权值单调上升的序列。 ### 5.1.2. 应用 结合下二叉搜索树的名字，肯定是为了搜索而生的了。 根据前面所提到的他所拥有的性质，我们可以造出一颗二叉搜索树可以回答以下询问： 1. 询问权值 $k$ 在序列中的的排名 2. 询问排名为 $k$ 的权值的大小 考虑如何回答这两个询问： * 对于第一种询问，我们考虑将权值与 $w_{rt}$ 的权值对比 * 如果 $k<w_{rt}$，那么这个值就出现在 $rt$ 的左子树中，向左子树走。 * 如果 $k=w_{rt}$，那么这个值就出现在这个点上，考虑这个点的排名即可。 * 如果 $k>w_{rt}$，那么这个值就出现在他的右子树中，向右子树走。 * 相似的，对第二种询问考虑，还是考虑将权值与 $cnt_{rt}$ 对比，考虑这个点的排名 * 如果 $k\le size_{ls}$ 则出现左子树中 * 如果 $k>size_{ls}$ 且 $k\le cnt_{rt}+size_{ls}$ 就出现在这个点上，返回这个点的权值。 * 如果 $k>cnt_{rt}+size_{ls}$ 就说明出现在右子树上，向右子树走。 以此考虑，便可完成上述的两种询问的查询。 接着，我们来考虑如何构造出一颗二叉搜索树。 考虑和上面相似的流程。 * 如果 $k<w_{rt}$ 则往左走。 * 如果 $k=w_{rt}$ 则给 $size_{rt}+1$ * 如果 $k>w_{rt}$ 则往右走。 直到结束或者到达一个空节点时，把这个信息录进去。 除此之外他还能支持删除操作等。 ### 5.1.3. 时间复杂度 知道了如何构造和使用二叉搜索树后，我们来考虑下二叉搜索树的时间复杂度。 显然，这个搜索次数与树高有关，也就是 $O(h)$。 最优情况应是树高最低时，也就是满二叉树时，复杂度为 $O(\log{n})$。 最劣情况则考虑下上面所提到的构造过程，只要输入是一个单调上升/下降的序列，就可以让二叉搜索树退化为一条链。 那个时候复杂度就变成了 $O(n)$。 所以二叉搜索树的搜索时间复杂度并不稳定。 这个时候我们就要考虑优化了。 * * * ## 5.2. 平衡树 上面提到了二叉搜索树的搜索时间复杂度并不稳定，所以实际使用时我们肯定不能用这么不稳定的数据结构了。 那么就得考虑下优化了，优化是什么呢？ 优化后就成为了平衡树。 了解到之前搜索复杂度不稳定的原因是因为树高不稳定，随时都有可能退化为链。 所以我们考虑一种可以控制树高的二叉搜索树，那他就成了平衡树。 考虑到这篇是树剖博客，所以我们这里指讲解和树剖有关的 Splay。 ### 5.2.1. 定义 * $\mathrm{rt}$ 代表根节点 * $\mathrm{rt}$ 代表节点个数 * $\mathrm{fa_i}$ 代表 $i$ 节点的父亲节点，特殊的，根节点没有父亲。 * $\mathrm{son_{i,0/1}}/\mathrm{ch_{i,0/1}}$ 代表 $i$ 节点的左右儿子编号。 * $\mathrm{si_i}$ 代表 $i$ 节点的子树大小，特殊的，叶子节点的子树大小为 $1$。 * $\mathrm{w_i}$ 代表 $i$ 节点的权值大小。 * $\mathrm{s_i}$ 代表 $i$ 节点上这种权值的个数。 * 每次操作后都要把操作的节点转到根上。 ### 5.2.2. 维护平衡 二叉搜索树之所以会被卡，就是因为不平衡导致的。 所以我们考虑如何维护 Splay 的平衡性。 首先根据上面定义的最后一条，我们得到 Splay 是通过旋转来维护整体平衡性的。 那么如何旋转呢？ 旋转有两种，分别为左旋和右旋，给张示意图吧：  从这张图里面我们可以看出，右旋就是把左儿子转上去，把自己转到右儿子那。 左旋则恰恰相反。 那么，对于节点的旋转，便成了这样： * 如果他是左儿子，就右旋。 * 如果他是右儿子，就左旋。 学会了旋转的方法，我们再来考虑下上面的最后一条： * 每次操作后都要把操作的节点转到根上。 但这个时候又会有一个问题，我们的节点转一次只能和上一个节点换位置啊，怎么转到根呢？ 难不成暴力转吗？ 答案是肯定的。 * 我们只需要直接暴力给目前这个节点一层一层转上去直到转到根就行了。 那这样的话 Splay 就写完了，那就可以去写题喽。 等等，再考虑下之前卡掉二叉搜索树的单调数据，用现在的 Splay 可以保证树高为 $\log{n}$ 吗？ 显然不行。 如果要深刻理解这种情况为什么会被卡，我们要先了解 Splay 能达到 $\log{n}$ 树高的原因。 * 每次操作后都要把操作的节点转到根上。 这个操作的意义在哪里呢？ 其实仔细观察我们会发现，在他路径上的点的深度，至少有 $-1$。 如图所示：   也就是保证了树高肯定会因为操作而趋向于 $\log{n}$。 再考虑下这种经典的错误，也就是单旋 Splay 被卡掉的原因，结合一张图来理解一下：  考虑这种情况，当爷父子三点共线的时候，我们转了半天只是给 $x$ 转上去了，没有改变树高，所以导致最后会被卡掉。 那如何改变这种情况呢？ 先转下中间的父节点 $y$，再转下要操作的节点 $x$ 即可。 可以考虑画张图来理解一下，这里借用下 `Enoch006` 画的图：      像这种判断三点共线并且考虑转两次的 Splay 被称为 双旋 Splay。 而前面那个会被卡的被称为 单旋 Splay。 那么 Splay 操作代码即为： int bh(int i) { if(t[t[i].f].son[0]==i) return 0; else return 1; } void rotate(int x) { int f=t[x].f,gfa=t[f].f; int x_=bh(x),fa=bh(f); t[t[x].son[!x_]].f=f; t[f].son[x_]=t[x].son[!x_]; t[x].son[!x_]=f;t[gfa].son[fa]=x; t[f].f=x;t[x].f=gfa; update(f);update(x); } void splay(int x,int y) { int f,gfa; if(x==y) return; while(t[x].f!=y) { f=t[x].f;gfa=t[f].f; if(gfa!=y) if(bh(f)==bh(x)) rotate(f); else rotate(x); rotate(x); } if(!y) rt=x; } ### 5.2.3. 操作实现 首先给出板子题：[P3369 【模板】普通平衡树](https://www.luogu.com.cn/problem/P3369) 在这题里面，我们要实现 $6$ 种操作，分别是： 1. 插入一个数 $x$。 2. 删除一个数 $x$（若有多个相同的数，应只删除一个）。 3. 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。 4. 查询数据结构中排名为 $x$ 的数。 5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。 6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。 了解了刚刚有关 Splay 最重要的操作 Splay 之后，这些询问只需要按照正常的二叉搜索树的形式来回答就行了。 **但是注意每一次操作完后 Splay 这个节点在根上。** 附上 [std](https://www.luogu.com.cn/paste/huugwblx)。 $\large{练习题}$ [P3391 【模板】文艺平衡树](https://www.luogu.com.cn/problem/P3391)。 * * * # 6. 实链剖分（LCT） 讲了这么久终于来到最**折磨**的一块了，打开这块之前请确保您已经深刻理解 Splay 并且不会写挂。 * * * ## 6.1. 定义 首先我们回忆一下前面的树链剖分，他们都采取了一种方式将树剖分为了链，那么对于 LCT，我们也要找到一种剖分的方式。 怎么做肯定取决于他的用途，所以在开头，我列举些 LCT 能维护的东西： * 查询、修改链上的信息（最值，总和等） * 换根 * 动态连边、删边 * 合并两棵树、分离一棵树 * 动态维护连通性 * 更多意想不到的操作 具体的大部分操作可以参考下 LCT 经典超强板子综合题：[P5649 Sone1](https://www.luogu.com.cn/problem/P5649)。 结合上面如此强的灵活性，我们得到了**极具灵活性的实链剖分**： * 对于一个点连向它所有儿子的边，我们自己选择一条边进行剖分。 * 我们称被选择的边为**实边**，其他边则为**虚边**。 * 对于**实边**，我们称它所连接的儿子为**实儿子**。 * 对于一条由**实边**组成的链，我们同样称之为**实链**。 * 请记住我们选择实链剖分的最重要的原因：它是我们选择的，**灵活且可变**。 * 正是它的这种灵活可变性，我们采用 **Splay** 来维护这些**实链**。 在实链剖分之后，我们就得到了 LCT 的重要部分：**辅助树**。 先给出辅助树的一些定义： 1. 辅助树由多棵 Splay 组成，每棵 Splay 维护原树中的一条路径，且中序遍历这棵 Splay 得到的点序列，从前到后对应原树「从上到下」的一条路径。 2. 原树每个节点与辅助树的 Splay 节点**一一对应**。 3. 辅助树的各棵 Splay 之间并不是独立的。每棵 Splay 的根节点的父亲节点本应是空，但在 LCT 中每棵 Splay 的根节点的父亲节点指向原树中 这条链 的父亲节点（即链最顶端的点的父亲节点）。**这类父亲链接与通常 Splay 的父亲链接区别在于儿子认父亲，而父亲不认儿子**，对应原树的一条 **虚边**。因此，每个连通块恰好有一个点的父亲节点为空。 4. 由于辅助树的以上性质，我们维护任何操作都不需要维护原树，辅助树可以在任何情况下拿出一个唯一的原树，我们只需要维护辅助树即可。 因为真的懒的画图，但是这个部分没图是真的很抽象，所以我只好拿 OI Wiki 上的了/kk。 若原树为：  其中加粗为实边，虚线为虚边。 则辅助树可能为：  考虑原树和辅助树的关系，可以得出以下几点： * 原树中的实链 : 在辅助树中节点都在一棵 Splay 中。 * 原树中的虚链 : 在辅助树中，子节点所在 Splay 的 Father 指向父节点，但是父节点的两个儿子都不指向子节点。 * 原树的 Father 指向不等于辅助树的 Father 指向（这一点一定要注意，自己的父亲数组不要搞混了）。 **P.S.: Splay 其实是 Tarjan 为了 LCT 所创造的，所以 Splay 对于 LCT 的需求可以完全满足。** 下面给出我代码中的几个定义： * $\mathrm{son_{i,0/1}}$ 分别表示左儿子和右儿子 * $\mathrm{st_i}$ 表示栈中的元素 * $\mathrm{w_i}$ 表示这个点的点权 * $\mathrm{s_i}$ 表示这个点的答案 * $\mathrm{f_i}$ 表示这个点的父亲 * $\mathrm{r_i}$ 表示翻转标记 * $\mathrm{ls}$ 表示 $\mathrm{son_{i,0}}$ * $\mathrm{rs}$ 表示 $\mathrm{son_{i,1}}$ ------------ ## 6.2. 实现 有了定义我们就可以开始实现一颗 LCT 了。 LCT 主要由几个核心操作组成，所以我选择将每个核心操作拆开讲。 首先是有关于 Splay 的部分： 这个部分我觉得其实没什么好讲的（前面已经讲过了捏，忘了的回去看！），看下代码应该就能找到不同并注意到了： void rotate(int x) { int y=f[x],z=f[y],k=(son[y][1]==x),w=son[x][!k]; if(ntrt(y)) son[z][son[z][1]==y]=x;son[x][!k]=y;son[y][k]=w; if(w) f[w]=y;f[y]=x;f[x]=z; pushup(y); } void Splay(int x) { int y=x,tot=0;st[++tot]=y; while(ntrt(y)) st[++tot]=y=f[y]; while(tot) pushdown(st[tot--]); while(ntrt(x)) { y=f[x];int z=f[y]; if(ntrt(y)) rotate((son[y][0]==x)^(son[z][0]==y)?x:y); rotate(x); } pushup(x); } 这里，我们发现有个函数叫做 ntrt，他的全称应该是 not root，因为属于 LCT 部分所以代码在下面了。他的意思是是否为当前 Splay 的根。 接着就是 LCT 部分了。 首先讲下比较基础的几个函数： ntrt：他的意思同上，代码也容易实现，考虑 LCT 中的 Splay 他的根节点是儿子认父亲，父亲不认儿子，使用这个特性即可： bool ntrt(int x){return son[f[x]][1]==x||son[f[x]][0]==x;} pushup：这个就和普通 Splay 中的差不多，用于得到这个点的答案值，不同的题目写法不同，这里给出 LCT 模板中的写法： void pushup(int x){s[x]=s[ls]^s[rs]^w[x];} 然后是有关懒标记与下传的 pushson 与 pushdown： LCT 所有的懒标记是翻转标记（为什么要用到翻转后面有解释，这边先讲讲怎么处理这个翻转），其实很好处理，每层下传即可，详情见代码： void pushson(int x){swap(ls,rs),r[x]^=1;} void pushdown(int x) { if(r[x]) { if(ls) pushson(ls); if(rs) pushson(rs); r[x]=0; } } * * * 接着是核心操作 **Access**： 他要实现的就是把从根到 $x$ 的所有点放在一条实链里，使根到 $x$ 成为一条实路径，并且在同一棵 Splay 里。**只有此操作是必须实现的，其他操作视题目而实现。** 先放上代码，再结合 OI Wiki 中的图讲下： void access(int x){for(int y=0;x;x=f[y=x]) Splay(x),rs=y,pushup(x);} 考虑这样一颗原树：  他的辅助树可能长成这样：  现在我们要 $Access(N)$。 实现的方法就是一步步转上去。 首先把 $N$ 转为当前 Splay 的根，再根据辅助树的性质，要将 $N,O$ 变为虚边。 由于父不认子，所以我们只要在转完后把 $N$ 的右儿子设为空即可。  接着继续旋转，把 $N$ 向上转一层，就得到了这张图：  重复上述操作，最后可以得到：  再到：  这样 $A,N$ 的路径就全为实边了，Access 操作也完成了。 其实考虑层层的转还是比较好理解的。建议自己画图手模下再理解下。 * * * 接着是另一个关键的操作 makeroot：将一个点变为当前树的根。 照例，先上代码： void makert(int x){access(x);Splay(x);pushson(x);} 我们会发现，makeroot 部分其实很简单： * 首先将 $x$ 到当前根拉到一颗 Splay 上 * 然后将 $x$ 旋转到树根上 * 最后我们考虑把树当为有向图，会发现，换根其实就是将 $x$ 到根的路径反向（这里建议好好思考下为什么） 所以这样就轻松完成了 makeroot 操作。 * * * 最后是 findrt，split，link，cut 操作，有了前面的 Access，Splay，makeroot，其实都非常好实现了： int findrt(int x) { access(x);Splay(x); while(ls) pushdown(x),x=ls; Splay(x);return x; } void split(int x,int y){makert(x);access(y);Splay(y);} void link(int x,int y){makert(x);if(findrt(y)!=x)f[x]=y;} void cut(int x,int y) { makert(x); if(findrt(y)==x&&f[y]==x&&!son[y][0]) f[y]=son[x][1]=0,pushup(x); } P.S.:这里给出的 cut 操作判断了边是否存在，同理，link 操作判断了边是否存在。 个人感觉想要真正理解 LCT，就把他当做暴力来理解（数据结构都这样吧）。 比如：我们要查询 $x$ 到 $y$ 的点权和，就把 $x$ 先弄成根，然后给 $y$ 和 $x$ 弄到一颗 Splay 中，然后直接给中间那段路径拿出来，完美解决。 这些代码建议好好消化理解，LCT 的代码是很短，但是挺难理解的。 * * * ## 6.3. 应用（板子） 前面的实现讲了之后，这个 [LCT 板子](https://www.luogu.com.cn/problem/P3690)是真板子了，这边直接奉上[ std](https://www.luogu.com.cn/paste/twvxdays)。 这里都是一些最基础的维护点权/判断连通性捏/kk。 ### **下面给点基础练习题** [P4312 [COI2009] OTOCI](https://www.luogu.com.cn/problem/P4312) [OTOCI - OTOCI](https://www.luogu.com.cn/problem/SP4155) 前面是双倍经验捏。 [P1505 [国家集训队] 旅游](https://www.luogu.com.cn/problem/P1505) 这题堆码量即可。 [P4847 银河英雄传说V2](https://www.luogu.com.cn/problem/P4847) 这题好像是这些题里面最难的，还要再写个 $query$。 [P3950 部落冲突](https://www.luogu.com.cn/problem/P3950) [P2147 [SDOI2008] 洞穴勘测](https://www.luogu.com.cn/paste/migf2vzo) [DYNACON1 - Dynamic Tree Connectivity](https://www.luogu.com.cn/problem/SP9577) 这个三个题比板子还简单。 ------------ ### 6.3.1.[DYNALCA - Dynamic LCA](https://www.luogu.com.cn/problem/SP8791) LCT 求 LCA LCT 是可以求 LCA 的！ 那怎么求 LCA 呢？ 先对其中的一个点 access（这里假定为 $x$），这样的话这个点到根的路径都变成了实边。 不难得到的是，$x,y$ 的 LCA 一定在 $x$ 到根的路径上。 所以 $x,y$ 的 LCA 指向 $x$ 的路径已经变成了实边，那么指向 $y$ 的路径就是虚边了。 这个时候我们只需要 access 一下 $y$，那么在这条路径上的最后一条虚边的父亲即为 LCA。 但是唯一需要注意的是求 LCA 的时候，link 和 cut 不能用 makert 写，不然的话父子关系会变。 附上 [std](https://www.luogu.com.cn/paste/qrlucye0)。 当然，也可以见[文章](https://www.luogu.com.cn/blog/Hok/solution-sp8791)。 $\LARGE{练习题}$ [P3302 [SDOI2013] 森林](https://www.luogu.com.cn/problem/P3302) 主席树的题，但是要求动态加叶子 LCA，可以用 LCT 也可以用倍增。 * * * ## 6.4. 应用（技巧） 看到这里说明你已经深刻理解（~~熟读并背诵~~） LCT 的板子了。 本章节将会讲一些重剖中比较模板的套路或是好题，方式是结合例题分析。 * **Warning:从此段开始难度直线上升，至少是紫。** * **P.S.：如果找不到锅了可以对下我的[出锅合集](https://www.luogu.com.cn/paste/ahc7lu2i)。** 题目讲解排序按照难度不一定单调递增。 那就开始吧： * * * ### **6.4.0.[P3203 [HNOI2010] 弹飞绵羊](https://www.luogu.com.cn/problem/P3203) 轻量化 LCT** 这道题算是这个版块中最为简单的了。 首先我们要考虑题意的转化。 $x$ 点的弹力装置可以把绵羊弹到 $x+k_i$ 个装置。 但是如果这个值大于 $n$ 则弹飞。 所以我们考虑如果 $x+k_i\le n$，就将 $x,x+k_i$ 连一条边。 否则不连边。 这里我们并不需要超级源点 $n+1$ 的做法，因为这题可以轻量化 LCT。 解释下这题为什么可以轻量化，重点在于： > * 题目保证造出来的是一颗树而不是森林。 所以 link 操作可以砍掉，直接连边就行。 cut 操作也可以砍掉，我们确定其父亲的位置，只要 $access(x),splay(x)$ 后，$x$ 的父亲一定在 $x$ 的左子树中，直接双向断开连接。 split 也可以砍掉，我们先 $access(x),splay(x)$，然后直接返回 $x$ 的 $size$ 即可。 所以就轻量化完成了。 附上 [std](https://www.luogu.com.cn/paste/6xbkzgml)。 * * * ### **6.4.1./6.4.2.[P4172 [WC2006] 水管局长](https://www.luogu.com.cn/problem/P4172) LCT 维护边权+MST+倒序操作** 这道题挺好玩的，试了下，一遍 pass 还是很爽的。 题意简述： > 给定一张动态图： > > * 询问 $u\rightarrow v$ 可能路径的最大边权的最小值。 > * 删除一条边。 首先这题肯定是想到 LCT 维护了，毕竟动态图。 那么考虑下删边操作就直接删，只是询问操作比较难处理。 而且给定的是动态图，LCT 解决的却是动态树问题。 再看下题意中 **可能路径的最大边权的最小值**，这句想到什么？ 对了，在 MST 上，这些值都是最小的。 那么题意就变成了维护动态 MST。 还是有点难度，因为我们有着删边操作，比较难以处理。 所以考虑倒序操作，把删边变成加边，初始化时把操作不会删掉的边全部加上。 那么就变成了一个只会加边操作的动态 MST。 考虑原本已经有一颗 MST，那么我们加边的时候，一定会产生一个环。 考虑找到这个环在加上这条路径前的最长路径的长度。 删掉那条最长的边，再加上这条边即可。（注意判断下这条加上的边是否更优。） 那这题貌似就华丽的结束了？ 不不不，还有一点还没考虑呢，那就是： > * LCT 如何维护边权？ 因为 LCT 没有固定的父子关系，所以不能考虑使用重剖那样的把边权下放到儿子的边转点技巧。 那这个时候我们该怎么办呢？ 直接 **拆点** 呗。 > 考虑把原本 $u\rightarrow v$ 边权为 $w$ 的路径化为，$u\rightarrow x\rightarrow v$，其中 $x$ 的点权为 $w$。 这下，题目就完美解决了。 **P.S.：注意这题询问的删边操作如何寻找，我用的 map 套 pair。** 附上 [std](https://www.luogu.com.cn/paste/aq886otj)。 $\large{练习题}$ [P2387 [NOI2014] 魔法森林](https://www.luogu.com.cn/problem/P2387) 维护 MST 的时候记得边权有两个即可。 首先按照第一个边权 $a$ 进行排序，那保证了造出来的树的 $a$ 一定是最小的。 然后对 $b$ 进行动态 MST 维护，每一次删边的时候考虑 $a+b$ 的值的影响，选取更优即可。 附上 [std](https://www.luogu.com.cn/paste/fjbatfpk)。 [P4234 最小差值生成树](https://www.luogu.com.cn/problem/P4234) 维护边权与 MST 变体的 LCT 捏。 考虑下把边按边权从小到大加进来，那每一次造出环的时候就应该去掉最小边权。 然后如果已成树就最大边权减去最小边权更新答案即可。 附代码 [std](https://www.luogu.com.cn/paste/6n9gbpoh)。 [DYNACON2 - Dynamic Graph Connectivity](https://www.luogu.com.cn/problem/SP9576) 详情可以见 [SP9576 解题报告](https://www.luogu.com.cn/article/a4nam4ep)。 [Best Edge Weight](https://www.luogu.com.cn/problem/CF827D) 讲解见[文章](https://www.luogu.com.cn/blogAdmin/article/edit/694725)了，其实我感觉他对于非树上的边就和动态 MST 差不多了。（懒癌不是用 LCT 写的。） * * * ### **6.4.3.[P4319 变化的道路](https://www.luogu.com.cn/problem/P4319) 线段树分治+动态 MST** 首先看到这题我们会发现是 MST 的板子，所以我们优先考虑上个 『6.1.1.』 的动态 MST。 然后我们发现了这个美妙~~傻逼~~题目的边有存在时间。 > * 题目说了每条边只在一个时间段中出现。 所以考虑套一个线段树分治，用线段树维护时间区间上的答案。 每次在符合的时间段里，就把边连上，做完后就断开即可。 附上 [std](https://www.luogu.com.cn/paste/qjx5pwrh)。 具体分析可以见[文章](https://www.luogu.com.cn/blog/Hok/solution-p4319)。 $\large{练习题}$ [P3206 [HNOI2010] 城市建设](https://www.luogu.com.cn/problem/P3206) 注意下线段树分治的 modify 修改的东西要单独存下。 然后和上面那道例题就没区别了。 附上 [std](https://www.luogu.com.cn/paste/q1pkosq5)。 * * * ### **6.4.4.[P2542 [AHOI2005] 航线规划](https://www.luogu.com.cn/problem/P2542) LCT 求动态割边/6.4.5.[P5622 [DBOI2019] 巫女的职责](https://www.luogu.com.cn/problem/P5622) LCT 求动态割点** 首先是 6.4.4.[P2542 [AHOI2005] 航线规划](https://www.luogu.com.cn/problem/P2542)。 发现是删边操作，发现不太好处理，所以考虑和前面一样离线倒序加边。 考虑先缩个点，把每个点双缩成一个点。 那么查询的时候就是链长度 $-1$（为什么是这样请读者自行推敲一二。） 然后好像就做完了？ 但不全然，缩完点之后记得 access 中要写成缩点后的点编号！ 附上 [std](https://www.luogu.com.cn/paste/yvfpmbcf)。（我卡了 $2$ 页，第一页是写挂了，第二页卡最优解，目前是最优解。） 如果怀疑自己 UB 强烈推荐 CF 的自定义评测。 然后是 6.4.5.[P5622 [DBOI2019] 巫女的职责](https://www.luogu.com.cn/problem/P5622)。 可以见[题解](https://www.luogu.com.cn/blog/Hok/solution-p5622)捏。 题意简述： > 1.$x,y$ 间连边。 > 2.单点修改权值。 > 3.求 $x\rightarrow y$ 上的割点权值和。 前两个操作都很好理解，重点在第三种操作上。 第三种操作的主要难点就在于如何动态求割点了。 首先我们考虑下之前静态求割点是怎么做的。 考虑建一颗圆方树，然后在圆方树上维护即可。 那怎么动态呢？ 其实很简单，我们只需要在连边前，判断这两个点是否连通，如果已经连通了，那连上这条边就会产生一个环，也就是点双，给路径上的边全部断开然后直接建圆方树即可。 这个复杂度是正确的。 下面给个略证： > 因为只有加边操作，所以任意一个点最多只会被合并一次（因为合并完后就成一个点了） > 那这样的话复杂度就是 $O(n)$，再加上 LCT 本身单点修改复杂度为 $\log n$，所以均摊后还是 $\log n$。 > 证毕。 然后就变成圆方树上查询树链信息了。 附上 [std](https://www.luogu.com.cn/paste/w1kf84ip)（卡了下卡到最优解第二了）。 $\large{练习题}$ [P5489 EntropyIncreaser 与 动态图](https://www.luogu.com.cn/problem/P5489) 就是动态求割点和动态求割边一起放进来了。 很好的一道练手题。 详情见[题解](https://www.luogu.com.cn/blog/Hok/solution-p5489)了。 我个人采取的方式是封装两个 namespace 做。 [P10657 BZOJ4998 星球联盟](https://www.luogu.com.cn/problem/P10657) 边双，也算比较简单的题。 详情见[题解](https://www.luogu.com.cn/article/tvbnob9a)。 * * * ### **6.4.6.[P4219 [BJOI2014] 大融合](https://www.luogu.com.cn/problem/P4219) LCT 维护子树信息** 知周所众的是，LCT 并不擅长维护子树信息。 但是这道题需要维护动态树的子树信息。 那怎么办呢？ 考虑下 LCT 为什么不能维护子树信息。 这一点是因为 LCT 中的父子关系并不确定。 也就是对于一个节点 $x$，对于他的实子树，肯定都是统计了的。 但是他的虚子树并没有统计进去。 所以我们考虑维护一个 $si2$ 数组即可。 这里给出定义： > * $\mathrm{si2_{x}}$ 代表 $x$ 的虚子树的信息。 比如这道题，就是权值和。 那么在 $pushup$ 函数中，我们就要额外更新下这个数组。 除此之外，还有 $access$ 中我们修改了一个实儿子为虚儿子，所以也要修改下。 最后还有 $link$ 操作的额外增加。 这样就完美解决了。 附 [std](https://www.luogu.com.cn/paste/9blletbm)。 **P.S.: link 时一定要注意，makeroot 要两次。** $\large{练习题}$ [CF1681F](https://www.luogu.com.cn/problem/CF1681F) 有很多种做法。 具体做法可以看 [CF1681F 解题报告（杂题选做）](https://www.luogu.com.cn/article/mobbbde2)。 ------------ ### **6.4.7.[P4271 [USACO18FEB] New Barns P](https://www.luogu.com.cn/problem/P4271) LCT 维护直径** 因为题目中有动态加边操作，形态也是森林，所以直接考虑使用 LCT。 是否在同一颗树中考虑使用并查集解决，那么剩下的问题就是如何求这颗树中离 $k$ 最远的点了。 考虑离他最远的点肯定是树的直径的两个端点之一，题意就变成了 LCT 维护直径。 那么新加一个点的时候，考虑加上原本直径的两个点，一共三个点，两两求个距离取最大即可。 std 见[题解](https://www.luogu.com.cn/blog/Hok/solution-p4271)了。 * * * # 7. 资料来源鸣谢 部分图片及资料参考 [OI Wiki 树链剖分](https://oi-wiki.org/graph/hld/)，[OI Wiki Splay 树](https://oi-wiki.org/ds/splay/) 以及 [OI Wiki Link Cut Tree](https://oi-wiki.org/ds/lct/)。 部分解法参考 lzyqwq 的题解。 树剖换根部分复制了[神犇 Farkas_W 的换根树剖笔记](https://www.luogu.com.cn/blog/Farkas/guan-yu-shu-lian-pou-fen-huan-gen-cao-zuo-bi-ji)。 部分长剖解法及图片参考 Ynoi 的[博客](https://www.luogu.com.cn/blog/Ynoi/zhang-lian-pou-fen-xue-xi-bi-ji)。 长剖板子中的图来自于 b6e0_ 的[博客](https://www.luogu.com.cn/blog/b6e0/solution-P5903)。