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

Hoks · 2023-12-28 12:17:59 · 算法·理论

目录

• 0. 前言
• 1. 附题单
• 2. 重链剖分基础
  • 2.1. 重剖求 LCA
  • 2.1.1. 引入
  • 2.1.2. 定义
  • 2.1.3. 时间复杂度
  • 2.1.4. 实现
  • 2.2. 重剖维护树上修改查询
  • 2.2.1. 如何转化
  • 2.2.2. 实现
  • 2.3. 基础题选讲
  • 2.3.1.[ABC294G] Distance Queries on a Tree 边转点技巧
  • 2.3.2.P4116 Qtree3 思路转化
• 3. 进阶提高篇（重链剖分的一些套路）
  • 3.1. P5838 [USACO19DEC] Milk Visits G 动态开点+多颗线段树
  • 3.2. Jamie and Tree 换根树剖
  • 3.3. P3401 洛谷树 拆位统计
  • 3.4. P7735 [NOI2021] 轻重边 染色+计数
  • 3.5. Dynamic Diameter 线段树上的奇怪 pushup
  • 3.6. Drivers Dissatisfaction MST 相关
  • 3.7. P2542 [AHOI2005] 航线规划 图转树+离线操作
  • 3.8. ...Wait for it... 树上拆点维护
  • 3.9. P5138 fibonacci 树上点权套斐波那契数列套矩阵快速幂
  • 3.10.P4175 [CTSC2008] 网络管理 重剖+整体二分
  • 3.11.Noble Knight's Path 重剖+主席树+二分
  • 3.12.Moonwalk challenge 重剖+二分+hash
  • 3.13.Tourists 圆方树上重剖+multiset 存信息维护
  • 3.14.GSS7 - Can you answer these queries VII 重剖+最大子段和
  • 3.15.P3925 思路转化+重剖
  • 3.16.Tree or not Tree 基环树+重剖
  • 3.17.P9808 [POI2022~2023R1] zbo 推式子转化+重剖
  • 3.18.P4719 【模板】"动态 DP"&动态树分治 ddp
  • 3.19.瓦里奥世界 Rujia Liu loves Wario Land! 启发式合并树剖
  • 3.20.P7671 [GDOI2016] 疯狂动物城 推式子+维护进阶版
  • 3.21.P9620 歌姬 树剖魔改 dfn 序
  • 3.22.MEX Tree Manipulation ddp 思想+找性质
  • 3.23.后记
• 4. 长链剖分
  • 4.1. 定义
  • 4.2. 实现
  • 4.3. 应用（板子）
  • 4.4. 应用（长剖优化 dp）
  • 4.5. P13363「TPOI-5B」回忆
  • 4.6. 后记（个人关于长剖看法）
• 5. 平衡树部分（Splay）
  • 5.1. 二叉搜索树
  • 5.1.1. 定义
  • 5.1.2. 应用
  • 5.1.3. 时间复杂度
  • 5.2. 平衡树
  • 5.2.1. 定义
  • 5.2.2. 如何维护平衡
  • 5.2.3. 操作实现
• 6. 实链剖分（LCT）
  • 6.1. 定义
  • 6.2. 实现
  • 6.3. 应用（板子）
  • 6.3.1.DYNALCA - Dynamic LCA LCT 求 LCA
  • 6.4. 应用（技巧）
  • 6.4.0.P3203 [HNOI2010] 弹飞绵羊 轻量化 LCT
  • 6.4.1./6.1.2.P4172 [WC2006] 水管局长 LCT 维护边权+MST+倒序操作
  • 6.4.3.P4319 变化的道路 线段树分治+动态 MST
  • 6.4.4.P2542 [AHOI2005] 航线规划 LCT 求动态割边/6.4.5.P5622 [DBOI2019] 巫女的职责 LCT 求动态割点
  • 6.4.6.P4219 [BJOI2014] 大融合 LCT 维护子树信息
  • 6.4.7.P4271 [USACO18FEB] New Barns P LCT 维护直径
• 7. 资料来源鸣谢

P.S.:洛谷文章区有了自带的目录！

-1.Update(25.9.6)

重构了部分猫猫觉得写的不好的部分。

0.前言

• Warning：打开这篇文章前最好确保自己已经学过了倍增，树上差分，dfs序等知识点。一定要学过线段树！！！

写这篇文章的主要目的是为了介绍树链剖分以及树链剖分的一些模型。

可能你们也注意到了，这篇文章的标题是 『从入门到入土』树链剖分。

而不是重链剖分或 LCT。旨在一次性从重链剖分开始讲到 LCT 结束。

那么，在正式开始之前，先写下致谢吧：

• 带我进树剖坑的大佬 lzyqwq。这里提供的题单的前身也正是他的博客中的树剖题单捏。
• 同时感谢让我学会了长剖的树剖姐姐 Ynoi 的博客。
• 还有 LCT 的题单前身正是大佬 zhiyangfan 的 LCT题单。
• 最后鸣谢下让我学会了 LCT 的大佬 FlashHu 的博客

1.附题单

『基础篇』重链剖分

『应用（折磨）篇』重链剖分

『究极折磨篇』LCT 题单

2. 重链剖分基础

2.1. 重剖求 LCA

2.1.1. 引入

重剖，与树相关，在树上的他，有一个最基础也是最重要的作用：求 LCA。

求 LCA 可谓是树上最基础也是最重要的部分了，基本所有的树上询问与路径有关的问题，都会考虑拆成 u\longrightarrow lca,lca\longrightarrow v 的方式来进行计算。

想必大家都会倍增求 LCA 吧，他的方法就是尝试往上跳 2^j 步，然后从大到小枚举 j。像二进制拆分一样把需要跳的步数变为二进制下的 0,1 来跳，就可以保证 \log{n} 的复杂度。

对于重链剖分而言，则是需要找到另一种跳跃的方式，使得跳跃的步数可以压缩，使得最终复杂度为 O(n\log{n})。

正如他的名字一般，重剖所采取的方法，就是把一颗树剖成一条条的重链，以一次至少跳掉一条重链的方式来保证其复杂度。

2.1.2. 定义

了解了重链剖分的原因之后，我们就可以正式开始学习重链剖分了。

先给出几个定义以及一张图（参考资料 OI Wiki）：

• 定义 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。
• 定义 轻子节点 表示剩余的所有子结点。
• 从这个结点到重子节点的边为 重边。
• 到其他轻子节点的边为 轻边。
• 若干条首尾衔接的重边构成 重链。
• 把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

个人认为，对于上面把落单的节点也看做重链还有一种解释方式，即：

• 重链的定义为若干条首尾相连的重边顶端，接上一条轻边。（除了根节点上接出的第一条重链）

那么落单的节点的情况便变为了『若干』 为 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 数组都未曾定义求过值。

考虑如何进行预处理，得出我们所需要的这些值。

因为是重链剖分，所以我们肯定要求出每个节点的子树大小，以及他所连的重儿子是谁。

数组的名称与意义说明：

实现时，我们考虑使用 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 了。

『模板』求 LCA 的代码。

2.2. 重剖维护树上修改查询

2.2.1. 如何转化

上一块引入部分，我们讲了重剖求 LCA 的方式，但是，重剖的用途远不止此。

要是重剖只能求 LCA 的话，还不如魏老师的好写好调且小常 O(n\log{n}) dfs 序大法呢。

所以接下来，我们要在树剖上套上数据结构，具体的例题便是重剖模板。

在这题里面，我们发现询问的东西，有了了 u,v 路径上的点权和。

而操作里面，也增加了修改一条链上的点权值。

（另外两种操作我们先暂且不考虑，优先考虑这两种。）

这个时候我们会想到什么呢？

要是询问的变成了一个区间，修改的也是一个区间和的话，就可以用线段树方便处理了。

那么我们怎么把树上路径转化为与区间相关的东西呢？

链不就能压为是一个区间吗，那我们只需要把树上路径转化为一条条链即可。

那怎么转化为链呢，这不就是重剖吗。

至此转化的问题已经解决了，但是还有一个问题：我们的线段树不是有一个序列的编号吗，那我们从树中拿下来的链编号怎么定呢？

这个时候就要涉及到 dfs 序了，还记得之前卖的那个关子吗（不记得回去看一下）。

• 我们把重儿子的遍历放在前面就是为了保证同一条重链的编号连续！
• 事实性而言，在一些特殊情况下，我们也可以改变遍历的方式用特殊的编号顺序来维护奇奇怪怪的问题。

那么，我们的 dfs2 就要加上两个数组，他们是：

写成代码也就是：

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 序，所以子树里的序号显然是连续的，直接区间修改查询即可。

最后是重剖模板代码。

树剖主要就是码量比较逆天，还是很需要练习的。

2.3. 基础题选讲

这里主要讲解一些蓝即以下的基础题捏，适合刚入门树剖的萌新看看。

P.S.:这里的题主要还是以码量为主，思路还都不是很难的，一定要自己上手练习。

那就直接开始吧。

2.3.1.[ABC294G] Distance Queries on a Tree 边转点技巧

题意已经非常清楚了，在此不再过多赘述。

这个时候我们会发现这道题他修改的是边权不是点权，好像无法维护了？

实际上，我们不难想到一种方法，将边权转为点权，而这种方法，也就是边转点技巧。

那对于一条边而言，我们的边权应该放到哪个节点上呢？

应该是下面的那个节点吧，那么我们就完成了边转点的操作。

对于查询呢？

这个时候要注意一个判断，因为我们把边权转点权了。所以 u,v 的 LCA 需要特判。

LCA 的点权是他上面的一条边的边权。

显然这个是查询不到的，所以千万不要加上！

那么边转点就算是说完了，可以先写个练习下。

倍增写的就不附了。

P4315 月下“毛景树”

正常的边转点之后，链赋值，链加。

然后线段树中维护最大点权即可。

（代码 不附了，写的很抽象）。

P4114 Qtree1

这道题首先是正常的边转点，然后接着的操作就变为了单点修改以及链查，还是很简单的。

当然做完后也可以尝试下QTREE - Query on a tree，这题是只能交 C 语言，可以练习下 C++\rightarrowC。

P3038 [USACO11DEC] Grass Planting G

这道题就先正常边转点，然后 u\rightarrow v 的路径上点权全部 +1，查询时直接拿 v 的点权即可。

2.3.2.P4116 Qtree3 思路转化

这道题呢，主要是一个思路上的转化。

我们先看下题，他查询的是 1\rightarrow v 上的第一个黑点，这种东西该怎么操作呢？

我们发现，从 1\rightarrow v 路径上的点，他的 dfs 序是单调递增的，也就是第一个黑点绝对是 dfs 序最小的。

所以我们考虑给每个黑点赋值为他自己的 dfs 序的值，每个白点赋值为 INF。

如此一来，题目中的查询第一个黑点就变成了查询 1\rightarrow v 上的最小值。

（代码就不贴了，我用 set 写的。）

3. 进阶提高篇（重链剖分的一些套路）

看到这里说明你已经理解了重剖而且写过了一定的基础码量题，现在，你可以开始真正应用重剖了。

本章节将会讲一些重剖中比较模板的套路或是好题，方式是结合例题分析。

• Warning:从此段开始难度直线上升，至少是上位蓝。

• P.S.：如果找不到锅了可以对下我的出锅合集。

题目讲解排序按照难度不一定单调递增。

那就开始吧：

3.1. P5838 [USACO19DEC] Milk Visits G 动态开点+多颗线段树

这题有个弱化版，可以先考虑下弱化版。

简要题意：

给定一颗树，树上每个点有个点权，询问 u,v 的路径上有没有给定的点权出现过。

首先考虑下弱化版先，发现弱化版点权只有两种，所以直接考虑分类讨论，不同的查找分类讨论一下处理。

或者是直接暴力做，给线段树里面加入这个区间是否有其中一种奶牛的标记就可以简单秒杀了。

接着来考虑金组的加强版，有 10^5 种点权，处理便困难起来了，如果像之前那样直接暴力做，想都不用像就会挂了。

所以我们考虑使用 STL 大法，因为题目只让我们判断有没有而不问个数，所以我们可以直接套上一个 set。

题目中也没有修改操作，所以 set 十分好维护，只要在造的时候加进来就可以了。

复杂度 O(n\log^3{n})。

附 代码。

显然这种做法不是很优，所以我们考虑一种优化的思想：

对着每一种颜色开一颗线段树，查询便变成了在对应颜色的线段树上查找是否出现过。

显然如果我们直接开 10^5 颗线段树空间会一言难尽，所以我们考虑用动态开点线段树维护，每个颜色也开个根节点。

（因为我懒所以就不再自己写代码了，可以参考下题解中神犇 lzyqwq 的代码。）

P3313 [SDOI2014] 旅行

这个题挺显然的，只是有点难写。

代码。

[ABC133F] Colorful Tree

这个题只需要注意下每次并不是真的修改。

所以每次只要查找给定颜色的边的总权值。

然后用原本的权值，减去给定颜色的边的总权值再加上给定颜色的边的数量乘以更改后的边权即可。

代码。

GOT - Gao on a tree

刚刚讲的那题，但是多组数据，卡掉了 O(n\log^3{n}) 的做法。

这边建议写成刚刚讲的那种方法，而不是 O(n+m) 的强大方式，当然这个方式最好也写下。

Santa's Gift

期望题，先展开下式子，然后因为颜色限制，所以考虑多颗线段树开拆即可。

代码。

Caisa and Tree

• 「保证 2 操作的数量不超过 50」的限制和 10 秒的时限太不牛了。让我们去掉这个限制并将时限改为 2 秒，再考虑怎么做。
• by lzyqwq

这里使用和神犇相同的做法谢谢喵。

考虑把质因数拆出来，不同质因数的树开一颗就行了。

代码。

3.2. Jamie and Tree 换根树剖

这道题是一个非常典的案例，这种题我称为换根树剖。

和他的名字一样，他的主要操作就是换根树剖。

也就是，这棵树的根可能会变，而他的查询，也是和子树有关。

其实就是分类讨论。

我们肯定不能每次换根每次重构，所以我们设定的那个根不妨称之为假根（正常应该都设置为 1 吧），那真正的根和假根会导致什么误差呢？

自然就是子树会产生一些微小的差距。

我们不妨先不要考虑求 LCA 这种困难的事情，直接考虑这题的查询操作。

那么根和查询点 x 的关系其实只有三种：

我们考虑画图即为：

那么各种情况也就非常好处理了：

1. 直接返回 x 子树和即可。
2. 考虑容斥，用全局和减去 rt\rightarrow x 路径上的最后一个点 y 的子树和。
3. 直接返回全局和即可。

完成了这个部分可以对修改有着不小的启发，我们考虑直接套相同结构。

因为我们已经知道对于根为 rt 时 x 的子树如何处理了，所以我们现在只需要求出根为 rt 时的 LCA(x,y) 即可。

依旧分讨，大概可以分为如下图的几种：

1. 在 y 子树中，LCA 即为 y。
2. 同 1，LCA 即为 x。
3. 这个 LCA 即为 LCA(y,rt)。
4. 同 3，LCA 即为 LCA(x,rt)。
5. 此时的 rt 在 LCA(x,y) 上面，LCA 自然为 LCA(x,y)。

由此我们发现其实 LCA 只会在 LCA(x,y),LCA(x,rt),LCA(y,rt) 中选择，且是其深度最深的一个。

那么 LCA(x,y) 子树加就和前面那个查询一样了，直接随便写下树剖就好了，附上 代码。

P3979 遥远的国度

这个是真的基本没区别，也没什么好说了，自己好好写一遍应该就能真正记住了。

代码。

3.3. P3401 洛谷树 拆位统计

这题也是一个比较套路的操作，就是拆位。

考虑把每一位的 0,1 情况拆出来考虑，就成了正常的题目了。

附上 代码。

P5354 [Ynoi2017] 由乃的 OJ

不过这题用拆位的方法不能过（或许可以卡常卡过去？），纯当练习好了。

3.4. P7735 [NOI2021] 轻重边 染色+计数

最折磨的典中典，这题是真的好，他应该不能算是一个固定的套路，但是好题还是讲一下吧。

• 我们考虑给每一次操作的两个端点染上独一无二的颜色。

没有太懂的话，具体的讲一讲，因为要将一条路径上的边修成重边，那么路径点染同色的操作就可以保证这条路径上点同色且所有边两端点同色，这样这些边就符合重边的判定了。

由于这些点被染成的是一种独一无二的颜色，是一定不与前面的颜色重复的，所以所有染色点连边的另一端一定与它的颜色不同，这样子这些边就自然而然的变成了轻边。

所以就美妙转化掉了，成了如何统计树的一段路径上同色相邻点对的数量。

这个时候就来考虑线段树维护了，但是由于重链相连接的地方可能会产生贡献，所以我们写的时候要分开写，也就是左边跳左边的，右边跳右边的。

给个代码看看吧：

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。

最后附上代码 代码。

P2486 [SDOI2011] 染色

这个是双倍经验吧。

3.5. Dynamic Diameter 线段树上的奇怪 pushup

这题，真的，是，太痛苦了！

我不知道刚学重剖的我当时怎么想的写了这个题，这个题是真的很痛苦。

题意很显然的，求直径的话我们可以弄两颗线段树，一个是维护的节点间距离，一个维护的是 dfn 在这个区间内的树的直径大小。

很显然对吧，接着就是痛苦实现了，这题的唯一痛苦就在实现上。

考虑下如何合并第二颗线段树中的值，也就是答案线段树中的值。

一颗树的一条直径是两个点之间的一条路径对吧，那两个子树就有两条直径四个点对吧。

这边可以证明出来最后树的直径肯定是在这四个点中两两组合中取一个最大。

请读者自行尝试证明一二。

接着有了这个之后我们只需要算出来两点距离就行了，拿另一颗线段树查询就完了。

真的很暴力！

附上 代码。

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

线段树合并板子，可以学下挺好的。

代码。

P4679 [ZJOI2011] 道馆之战

这个合并的东西有点不一样，是二维的好玩。

代码。

P9555 「CROI · R1」浣熊的阴阳鱼

这题合并的时候注意顺序！注意顺序！！注意顺序！！！

代码。

Tavas on the Path

这题折磨的，一定要做好心理准备。

代码。

Moonwalk challenge

这题使用奇怪 pushup 的做法可以直接把整段的字符串弄出来然后再数次数。

虽然过不了，但是练习码力还是很好的。

• 如果说你用的是 find 查询次数，那写到最好情况应该是 TLE on #15。
• 如果你写的是 hash 查询次数的话，那最好应该是写到 RE on #4。

亲身实践得到的/cf。

代码（使用 find 实现的 TLE on #15）。

代码（使用 hash 实现的 RE on #4）。

3.6. Drivers Dissatisfaction 重剖+MST

这题看到后我们会有一个比较显然的想法，把钱全部花在一条边上，因为如果我花在两条边上，不如花在一条代价更小的边上。

他相当于是固定了一条边肯定要在树中的最小生成树，参考板子严格次小生成树中的做法，先求最小生成树然后考虑换边即可。

Best Edge Weight

讲解见文章了，其实我感觉这题挺像动态 MST 的？

MST Unification

代码。

Edges in MST

代码。

（鬼知道我为什么写了 6.2 KB，仔细一看原来是板子人）

3.7. P2542 [AHOI2005] 航线规划 图转树+离线操作

里面保证了这么一句话：在整个数据中，任意两个星球之间最多只可能存在一条直接的航线。题目保证不存在重边，而且互相连通，又是无向图...想到了什么？

图可以变为树啊！也就是说，我们需要动态的维护树上点之间的距离。

然后树剖维护树上的边权，这样就可以轻而易举的求出树上两点之间的距离了。

直接将一个环内的点之间的边权赋为 0 不就行了！

读入询问，逆序处理。

先随便在原图中求出一棵生成树。

然后用那些没被删除的非树边先更新一遍当前的边权。

最后树剖猛猛做。

注意经典边转点细节，不要修改 LCA!!!!!!

附上 代码。

练习题

OTOCI - OTOCI

P4312 [COI2009] OTOCI

两题通用 代码。

P.S.：这两题是没有强制在线，原题是用交互保证在线的，现在可以离线！

P3950 部落冲突

代码。

3.8. ...Wait for it... 树上拆点维护

考虑第一篇题解里的做法，把每个点拆成出点和入点，权值为无穷大。

接着一个物品单独造一个点，和他前面后面的点连起来。

对于查询而言的话，就是暴力每次扫一个删一个。

复杂度因为是删掉物品，所以可以保证。

很简单对吧，特别难调！

附上 代码。

P5478 [BJOI2015] 骑士的旅行

代码。

Duff in the Army

这三题好像没有什么区别/kk。

3.9. P5138 fibonacci 树上点权套斐波那契数列套矩阵快速幂

这题的话，我认为主要的重点是一个结论的背诵。

也就是:

这个结论非常重要，基本涉及 fibonacci 数列的题大概率用到吧。建议熟背。

有了结论之后我们就可以开拆式子了。

首先把 u,v 的距离弄出来，考虑下用与根的距离算，也就是 dis_u-dis_v+k。然后用上面那个公式给式子拆开做即可。

也就是令 m=dis_u,n=k-dis_v 之后换算式子，左右当做两个 tag 写就可以了。

附上 代码。

3.10.P4175 [CTSC2008] 网络管理 重剖+整体二分

这道题是我第一次接触整体二分/kk。

首先概括下题意：带修改树链第 k 大问题。

应该算是一个经典问题了。

首先说下整体二分，就是用分治的思想一次性完成所有的操作，其中包括了修改与查询等。最后一次输出。

这道题也就是相当于把整体二分上树。

考虑把每个操作都标记一个时间戳 cntt，保存在操作记录数组 t 中。

由于树初始带有点权，所以就相当于初始单点修改了 n 次，把每个点改为对应的点权。

更改点权就相当于先删除后增加点权了。

剩下的就是整体二分的套路了。

附上 代码。

P3250 [HNOI2016] 网络

3.11.Noble Knight's Path 重剖+主席树+二分

首先这题要保存多颗树的状态返回查询，所以考虑使用主席树。

其次，这道题要找到路径上的第 k 个没有被入侵过的城堡。

发现这个查询有单调性，也就是排名单调性。

所以考虑二分，只要在对应版本的主席树上二分即可。

附上 代码。

3.12.Moonwalk challenge 重剖+二分+hash

折磨的黑，前面的练习题里面提到过了，所以我还是讲下好了。

首先讲下部分的做法，考虑直接暴力开搞。

给路径上的字符串直接整出来，然后对着 hash 开跑匹配。

很好的是，hash 要的空间是 2.6\times 10^{11}。而且至少得是 long long，而且容易被卡。

所以考虑优化。

预处理出每条重链向上和向下的 hash 值，然后像之前一样。

对于跨越重链的部分就用 u\rightarrow lca,lca\rightarrow v 的方法拆分即可。

发现这个 hash 他具有可减性与单调性，所以考虑套上二分。

附上 代码。

Misha and LCP on Tree hash+重剖。

代码。

P6088 [JSOI2015] 字符串树 可以 hash+重剖捏

P9399 「DBOI」Round 1 人生如树 重剖+hash+二分。

详情可以见题解。

P9997 [Ynoi2000] pmpkmp

这题我不评价了，CF1045J 加强版。

见题解吧。

代码 不能给（题目限制），但是可以私信找我要。

3.13.Tourists 圆方树上重剖+multiset 存信息维护

这题挺板子的，但是属于一个典例了，所以还是拿出来讲下吧。

首先发现这题是个图，所以没法做了。

我们考虑使用广义圆方树，把图变为树。

然后再在树上使用树链剖分。

但是要注意的是，这题不能在圆点改权值时，改周围所有方点的权值，不然会被菊花图卡到 n^2。

所以对于一个方点，multiset 里面存它所有子节点的权值。然后修改一个圆点时，就只需要动它父亲的 multiset（它的父亲必然是一个方点）。询问时，仍然可以正常询问，只不过如果 lca 是一个方点，那还要额外计算 fa[lca] 的权值对答案的贡献。

这样就做完了。

代码 就不附了，这题我写的太抽象了。

3.14.GSS7 - Can you answer these queries VII 重剖+最大子段和

这个很经典啊，但是我忘记给他拿出来了，现在补下讲解。

首先是最大子段和这个经典操作。

考虑线段树维护几个信息：

那就很好处理了，这边我就讲下 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;
}

合并的时候，考虑

即可。

对于树链上的查询，我们考虑把 u\rightarrow v，分为 u\rightarrow lca,lca\rightarrow v，然后拿 resl 维护左边答案，resr 维护右边的答案，最后合并即可。

注意，这里合并的时候要把 resl 或者 resr 的 sl,sr 翻转一下，因为树上路径不是从 lca 出发向 u,v 走的，而是从 u 到 v 的。

附上 代码。

3.15.P3925 思路转化+重剖

可以见我的题解喵，代码见题解了。

对了，吐槽一句，这个题目的名称他是敏感词，这点我真的没绷住。

update：不行了我要再来吐槽一次，这个为啥都是敏感词啊。

首先是简要题意：

• 每个点都有一个权值。
• 对于每个点，把他的子树中的所有点的权值从小到大排序，记答案为权值大小乘以排名。
• 询问每个点的答案的和。

如果没有看的很懂的话，可以看题目解释这张图：

然后我们来考虑下怎么做。

首先考虑暴力，给每颗子树都弄个堆暴力计算，这样的复杂度是 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 提取出来。

接着申明一些定义：

那么对答案的贡献式即为 \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 即可。

原本我以为，我写完这个冷门树剖题的题解就不会再与这题相见了。

结果就在今天上午的模拟赛里的 G 题就和这题基本没有区别。

只是从求最大价值变为了最小价值，并且询问每个点对总答案的贡献。

很快啊，我就开始想树剖做法了。

然后发现树剖他是通过离线合并了统计答案的过程来做的，所以无法完成每个点的询问。

这下就给我气到了，出了个原题可用树剖的题还把我最喜欢的树剖做法卡了。

于是脑子就被我扔掉了，我们考虑使用启发式合并平衡树来解决这个问题。

怎么启发式呢，考虑用重链剖分来启发式合并，因为重儿子有着子树大小至少为一半的特性。

所以我们的复杂度是有保证的，为 O(n\log^2n)。

这下就做完了，实现稍微有点难度，可以见代码。

这里给出的代码是我赛场的时候写的，赛场那题是多测，先读点权再读边的。

这里的傻逼作者没写 FHQ 的原因是因为不会，学过 Splay 的原因是因为学了 LCT。

虽然赛场上我是给这题写出来了，但是因为做法巨复杂，所以喜提最抽象解。

听讲课的时候我才发现，原来 G 题他有个题目条件保证为二叉树，所以可以直接上树状数组，而且正常还可以用线段树合并。

还有个傻逼赛场上写的时候没有清空重儿子数组一直 TLE 0，卡了半小时，我不说是谁啊。

3.16.Tree or not Tree 基环树+重剖

也可以见 题解 捏。

首先我们考虑下题目中的基环树要是变成树该怎么处理。

用每个线段树维护重链上的 1 边数量 cnt。

如果取反就直接把数量改为长度 r-l+1 减掉原来的数量 cnt 即可。

考虑翻转时存在两种情况：

1. 将 0 改为 1 时，1 边连接的极大连通块数量会 -1。
2. 将 1 边改成 0 边时，极大连通块数量会 +1。

那么让初始答案为 n，每次操作在线段树修改时顺带统计一下 1 边变化量以更新答案就好了。

那面对基环树呢？

考虑转化为树，把环缩点之后就成了一颗树。

缩点很简单，直接拓扑排序打标记即可。

剩下的环上的点考虑再开一颗线段树维护，就可以顺利完成此题了。

附 代码。（因为没用 namespace 封装也没用 struct 封装所以很臃肿。）

P4949 最短距离 更简单一点，无需缩点，这题考察的是树和基环树间的联系。

3.17.P9808 [POI2022~2023R1] zbo 推式子转化+重剖

这边我就转载下题解吧，也可以去题解文章那里看捏。

美妙树剖，比较套路了吧，反正一眼秒了。

原本不想补题解的，但是做到这题还是我的御用纯情娇羞可爱内向小男娘 Loser_Syx 把这题推给我了捏。

题目这么大个式子摆在眼前肯定先考虑暴力化简下啊。

题目给定的一个函数外面再套求和肯定是不太好做的，所以考虑先拆里面。

里面的直接使用树上距离公式就行了（注意这里的深度是指到根节点的距离）。

用这个式子就可以把之前那个又臭又长的式子破开成为：

然后把这里面好算的东西拿出来破开：

（虽然我感觉很惊讶，但是另一篇题解后面的这个系数好像写错了，应该是 4，原因是把从 1 开始变为从 i+1 开始应该再乘上一个 2 的系数。）

然后把前面一坨和后面那一坨分开，也就是令

这里都是一些美妙推式子喵。

P4211 [LNOI2014] LCA，这题典中典了，不多介绍了。

附 代码。

P5305 [GXOI/GZOI2019] 旧词，这题就是上一题的简单推广。

附 代码。

P5559 失昼城的守星使

这个题和 LCA 那题差不多吧，以这个为基础大力推就完了。

详细的 solution 可以看我的 题解 喵。

Arkady and a Nobody-men

和板子题 LCA 差不多，但是要卡常，可以当做练手题，没过的话全加 inline 就行了。

代码 在题解里了。

3.18.P4719 【模板】"动态 DP"&动态树分治 ddp

经典中的经典，ddp 板子。

首先，考虑把题目中的修改操作去掉，那么，这题就变成了一个非常板子的树形 dp。

考虑下这个 dp 的式子，先设计状态：\mathrm{f_{i,0/1}} 表示选/不选第 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 去掉了，状态转移方程式即为：

这个时候我们发现，虽然 \sum 没了，但是 f_{i,1} 的方程中还有一个顽固的 a_i。

所以我们直接考虑把 a_i 合并进 g_{i,1} 中，详细的定义即为：\mathrm{g_{i,1}} 表示 i 点的所有轻儿子都 不 选且选 i 点的最大权独立集。

这个时候第二个式子也就变成了：

接下来的问题就是如何快速维护 f_{i,0/1},g_{i,0/1} 了。

思索一下学过的优化 dp 的各种方式，有 DS 优化，矩阵优化，斜率优化等等。

首先排除斜率优化的可能性，仔细思索一二会发现 DS 也不好优化，所以这里考虑能否使用矩阵优化。

矩阵优化的核心所在，便是使用转移矩阵与矩阵乘法，利用快速幂使复杂度从 n 变为 \log n。

但是我们这个式子里又是 \max 又是 + 的，怎么化为矩阵呢？

不难发现，\max 是不能转化为 + 的，但是 + 可以转化为 \max。

所以我们考虑先把式子转化为一个大 \max 的形式，即为：

这样的话转移方程里就只剩下 \max 了。

但是矩阵乘法明明是乘法，哪来的 \max 和 + 呢？

这个时候就要使用广义矩阵乘法了。

为了满足结合律，并且用上 \max 和 +，其计算方式即为：

这样定义的广义矩阵乘法是满足结合律的，笔者不会证但是可以感性理解一下，\max 和 + 都是满足结合律的，所以将这两者结合时也是满足结合律的。

这里右边的那个矩阵推出来的方法就与正常矩阵乘法题目的推法类似，这里不再赘述。

但是这里有个坑点，因为转移矩阵存在 i 上，而前面的那个矩阵是存在 son_i 上的，这样的乘法顺序是有问题的，需要调转一下顺序，即为：

接着对于每次修改点权，只需要修改 g_{i,1}，一路向上跳修改 f_{i,0},f_{i,1} 即可。

附 代码。

P.S.:这里把广义矩阵乘法部分循环展开了，速度快亿点。

P4751 【模板】"动态DP"&动态树分治（加强版）

这题，号称卡了树剖，但是我们还是可以莽过去，重点优化即为以下三点：

1. fread 快读。
2. 循环展开广义矩阵乘法。
3. 减少函数调用。

第一点和第二点都十分简单，重点在于第三点。

不难发现，我们函数中有个叫 query 的函数，用来查询线段树上一段区间的值。

但是仔细观察下我们查询的区间，这些区间都正好对应线段树上的一个点。

所以我们根本没有必要写这个 query 函数，只要记下每个点要查询的区间对应的线段树上的点即可，查询时直接返回线段树上这个点的值就行了。

附上 代码。

P5391 [Cnoi2019] 青染之心

这题不是 ddp，但是树上背包还是很有意思的。

本题的难度就在于如何看出来是个树的问题，看出来后就可以轻松秒杀了。

附 代码。

P5024 [NOIP2018 提高组] 保卫王国

这题有非 ddp 的倍增做法，但是从练习 ddp 的角度来说还是写 ddp 好了。

采取第一篇题解中的算法一，对着模板的矩阵进行修改。

首先因为我们要求的值需要取 \min，所以广义矩阵乘法的地方要修改为 \min。

其次因为要取 \min，所以初始值全部赋为 \infty。

同时修改矩阵转移式为：

对于必选和必不选的问题，只需要修改为 \infty,-\infty 即可。

P.S.:有个消愁因为把 dfn 写成了 id 导致 48 分，警钟撅烂。

附 代码。

3.19.瓦里奥世界 Rujia Liu loves Wario Land! 启发式合并树剖

吐槽一句，这题能算是板子题吗，感觉这种套路应该是能算板子的，但是我只做过这一道启发式合并树剖。

简要题意：

• 给定 n 个点的森林，每个点都有权值，有三种操作，总共 m 个操作和模数 k。
• 1. 给定点 u,v，给点 u,v 间连一条边，若已连通则忽略。
• 2. 给定点 x 和值 val，表示把点 x 的权值改为 val。
• 3. 给定点 u,v 和值 w，查询 u\rightarrow v 的路径上点权小于等于 w 的点个数，以及点权小于等于 w 的点的点权乘积对 k 取模。如果不存在这样的点则只输出一个 0。

抓住题面重点，虽然好像都挺难办，但最优特色的还是强制动态连边。

一个树上路径查询问题，首先想到重剖和动态树。

强制动态连边，考虑使用动态树如：LCT 解决。

接着来观察下查询操作，是给定一个值根据这个值比大小查询。

一眼 LCT 不可做的样子。至少我不会。

那么只能来尝试重剖了，但是重剖必须要树的形态固定才能剖，貌似很难解决。

接着发现没有动态删边，可以考虑使用启发式合并的方法来每次暴力重构，把小树的答案接到大树中。

那么到现在主体思路已经确定下来了，即为启发式合并重剖。

接着来考虑怎么维护这个题目中要的信息。

P3899 [湖南集训] 更为厉害

4.5. P13663 「TPOI-5B」回忆 - 洛谷

非常荣幸有生之年能在这篇笔记中写入一道自己的题目，虽然说比较烂比较简单啦。

可以见完整题解喵。

首先你可以发现这个 MEX 显然是假的。

下面这块主要证明了单调性，较易理解读者可以考虑跳过。

因为对于一个点 u 假设其一个儿子为 v，且 v 的权值为 f_v。

那么在 v 的子树中就有 0,1,2,\dots,f_v-1。

显然的是 v 的子树肯定是 u 的子树，所以 u 的子树里就肯定有 0,1,\dots,f_v。

所以 u 的权值 w_u 肯定满足 f_u\ge f_v+1。

那既然对于每个儿子都要满足，我们就有 f_u=\max\limits_{v\in T_u} (f_v+1)。

接着再转化一步，我们不妨把这个一步一步往上传贡献直接变成，一个点 u 通过他子树内的叶子集合 S_u 进行计算。

若定义 dep_u 表示 u 点的深度，那么 f_u=\max\limits_{v\in S_u}dep_v-dep_u。

那我们不妨来考虑加入一个叶子后对上面的点的影响。

加入一个点后最多只是在最深的叶子下多挂了一个叶子，那么也就是 \max\limits_{v\in S_u}dep_v 自增 1，也就是 f_u 自增一。

而且这个 f_u 肯定是不能变的更小的，所以只能自增和不变两种可能性。

然后就很容易的可以注意到这里是有一个单调性的。

具体的，设新增的点为 x，如果对于点 u，x 的加入使得 f_u\leftarrow f_u+1，那么对于 v（v 在 u\rightarrow x）上，我们就有 v 一定会因为 x 的加入而更新。

因为 S_v\subseteq S_u，所以 \max\limits_{i\in S_v}dep_v\le\max\limits_{i\in S_u}dep_i。

然后我们又有 x\in S_u,x\in S_v，且 dep_x 是 S_u 中的 dep 最大值，所以 dep_x 肯定就是 S_v 中的最大值了，自然也就可以更新 f_v。

于是就说明了这个权值 f 是单调的，MEX 也只是吓唬人的。

到这里你就可以用重剖去做掉了，但复杂度不够优秀。

事实上我们可以发现这个权值 f 他非常契合长剖的性质（f 的值其实就是长链长度嘛），所以不妨考虑一下长剖做法。

然后关于长剖我们知道的是经典性质：继承长儿子暴力合并短儿子可以做到线性复杂度。

因为 f 是单调增的，所以我们不妨来考虑没加入一个点后对于答案的变化。

对于一个点 u，我们枚举他的所有短儿子 v，再枚举短儿子所在的长链点 x，同时枚举 u 长链中的同深度的点 y。

如果编号上 x<y，那么说明 x 先于 y 插入，也就是 u 这个点的长链本来在 x 处后来变到了 y 处，那么就将当前的标记结算并继承短儿子的标记。

对于长儿子，直接上传自己的权值和加法标记就行。

最后回到链顶之后再结算下整条链的标记就行了。

这样讲还是太抽象了，这里结合代码讲一下具体的实现方式。

这里并没有必要像 Register_int 一样写链表，可以写的很精简也很快（）。

inline void dfs2(int u,int top)
{
    dfn[u]=++cnt;id[cnt]=u;
    if(son[u]) dfs2(son[u],top);
    else ed[top]=cnt;
    for(int k=head[u];k;k=nxt[k])
    {
        int v=to[k];
        if(v==son[u]) continue;dfs2(v,v);
        for(int i=dfn[v],j=dfn[u]+1;i<=ed[v];i++,j++) if(id[j]>id[i])
            ans[id[j]]+=tag[top]+g[j],g[j]=mod-tag[top],id[j]=id[i];
    }tag[top]=(tag[top]+a[u])%mod;g[dfn[u]]=mod-tag[top];
    if(u==top) for(int i=dfn[u];i<=ed[u];i++) ans[id[i]]+=tag[u]+g[i];
}

其中我们可以直接把当前长链的权值和存在链顶 top 中，也即为 tag[top]，因为我们是自底而上的一个过程，所以每时每刻这个 tag[top] 实际上表示的都是当前点 u 所在长链的权值和。

• 如果 k>w_{rt} 则往右走。

直到结束或者到达一个空节点时，把这个信息录进去。

除此之外他还能支持删除操作等。

5.1.3. 时间复杂度

知道了如何构造和使用二叉搜索树后，我们来考虑下二叉搜索树的时间复杂度。

显然，这个搜索次数与树高有关，也就是 O(h)。

最优情况应是树高最低时，也就是满二叉树时，复杂度为 O(\log{n})。

最劣情况则考虑下上面所提到的构造过程，只要输入是一个单调上升/下降的序列，就可以让二叉搜索树退化为一条链。

那个时候复杂度就变成了 O(n)。

所以二叉搜索树的搜索时间复杂度并不稳定。

这个时候我们就要考虑优化了。

5.2. 平衡树

上面提到了二叉搜索树的搜索时间复杂度并不稳定，所以实际使用时我们肯定不能用这么不稳定的数据结构了。

那么就得考虑下优化了，优化是什么呢？

优化后就成为了平衡树。

了解到之前搜索复杂度不稳定的原因是因为树高不稳定，随时都有可能退化为链。

所以我们考虑一种可以控制树高的二叉搜索树，那他就成了平衡树。

考虑到这篇是树剖博客，所以我们这里指讲解和树剖有关的 Splay。

5.2.1. 定义

• 每次操作后都要把操作的节点转到根上。

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 【模板】普通平衡树

在这题里面，我们要实现 6 种操作，分别是：

1. 插入一个数 x。
2. 删除一个数 x（若有多个相同的数，应只删除一个）。
3. 定义排名为比当前数小的数的个数 +1。查询 x 的排名。
4. 查询数据结构中排名为 x 的数。
5. 求 x 的前驱（前驱定义为小于 x，且最大的数）。
6. 求 x 的后继（后继定义为大于 x，且最小的数）。

了解了刚刚有关 Splay 最重要的操作 Splay 之后，这些询问只需要按照正常的二叉搜索树的形式来回答就行了。

但是注意每一次操作完后 Splay 这个节点在根上。

附上 代码。

P3391 【模板】文艺平衡树。

6. 实链剖分（LCT）

讲了这么久终于来到最折磨的一块了，打开这块之前请确保您已经深刻理解 Splay 并且不会写挂。

LCT 全称 Link-Cut-Tree，应该算是最简单的用于实现动态树问题的数据结构，擅长树链信息。

6.1. 定义

在学习 LCT 之前，我们先来思考下重剖的局限性。

重剖的桎梏就在于必须要离线。

因为你要先得出对于一颗树的轻重剖分后才能维护一系列的操作。

虽然重剖也存在猎奇的启发式合并重构做法，但这显然不是擅长的。

所以为了解决动态树问题，首先我们就要让这个剖分方式变得灵活可变。

由此我们引入一种新的剖分方式：实链剖分。

不同于重剖，实链剖分的虚实儿子可以在符合性质的情况下自由变换。

具体的，LCT 通过维护和原树对应的辅助树来实现各种操作。

剖分所需要满足的性质即为辅助树性质，具体定义如下：

• 辅助树由若干个 Splay 组成，且中序遍历满足其在原树中的深度单增（即为一个 Splay 对应一段链）。
• 一个 Splay 维护一块实链连通块，Splay 之间由虚边相连，且连接的父亲就是这段链在原树上的父亲。

值得注意的是 LCT 中的虚边有一个特殊且重要的性质：父不认子，子认父。

具体的原因会在之后解释。

实际而言， LCT 中的 Splay 会进行一些特异化处理，这点也是需要注意的，不能混淆。

接下来是一些下面代码中的数组意义：

6.2. 实现

Splay

首先是有关于 Splay 的实现，大体与前文中的 Splay 相同（忘了回去看喵），特异化处会用注释标出。

void rotate(int x)
{
    int y=f[x],z=f[y],k=(son[y][1]==x),w=son[x][!k];
    //这里这个 if 要优先，即为特异化
    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;
    //下面这段传 tag 也是，转前先把前面的 rev tag 传了，手写栈下传常数小点
    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(x)，用来判断 x 是否为当前 Splay 的根。

其实现实则便是依赖于 LCT 的父不认子，子认父性质，非常好写：

bool ntrt(int x)
{
    return son[f[x]][1]==x||son[f[x]][0]==x;
}

而 pushup(x) 与 pushdown(x) 函数即为正常的维护信息函数，不再过多解释后面有完整代码。

Access

LCT 的核心操作是 access(x)，正如其名，其作用即为：打通 x 到原树根的路径，即将 x 和原树根放到同一个 Splay 里。

假设原树根为 rt，那么经过 access(x) 后，x 所在 Splay 维护的实链就是原树 rt\rightarrow x 的路径。

这个操作的意义非常明显，因为信息与形态全是用 Splay 来维护的，所以只有在同一个 Splay 里时我们才能得到想要求的东西/做想要的操作。

比如说换根为 x 操作，自然就需要先把 x 和原树根放到同一个 Splay 中，再用 Splay 实现换根。

那 access(x) 如何具体实现呢？

我们不妨考虑这样一颗原树：

他有一个符合条件的辅助树如图：

（注意区分下图中的左右儿子关系喵）

接下来我们来尝试 access(10)。

首先我们要让 10 成为当前 Splay 的根，但这个例子不是很好 10 已经为根了那就没有太大区别。

然后我们要打通 10\rightarrow7 这条路径，就要先把 7 转到其 Splay 的根节点。

然后我们可以得到如图：

接下来我们要将 10 与 7 联通，那么就要把 7\rightarrow11 这段路径扔掉先。

也就是把 7\rightarrow11 改为虚边，7\rightarrow10 改为实边，最后即为：

至此 10 所在这棵 Splay 维护的即为 1\rightarrow10 这条路径。

形式化的描述就是假设当前点为 x，那么我们先把 fa_x 转到上去，再修改 fa_x 的右儿子为 x。

写成代码而言也是精简的不得了：

void access(int x)
{
    for(int y=0;x;x=f[y=x]) 
        Splay(x),rs=y,pushup(x);
    //y 即为 lstx
}

Makert

makert(x) 是是 LCT 中另一个重要的函数，其作用为将 x 变为原树的根。

请注意区分原树和辅助树的概念，不要混淆二者的树根。

Splay(x) 操作只是将 x 转到了当前 Splay 的根而不是将其变为了原树根。

这两者最大区别就在于是否改变节点在原树上的深度性质。

因为辅助树保证每个 Splay 的中序遍历是原树从上到下的一条链，所以如果你把一个链下面的点变为新树根之后，中序遍历就要倒过来。

说了这么多也该正式考虑下怎么实现 makert(x) 操作了。

首先我们肯定要让 x 能到达原树根，也就是先进行 access(x) 操作。

接着我们惊人的发现，其实只需要 Splay(x) 再交换 x 的左右儿子就可以完成换根操作了。

比如对于上面那个原树的例子，我们不妨把他画成由根指向叶子的有向图：

接下来我们进行换根操作，把 11 变为新的树根。

然后原树就变成了这样：

我们惊奇的发现，其实需要调转方向的只有 1\rightarrow11 这条路径。

那我们拿出现在辅助树的图：

你发现现在我们要让 1\rightarrow3\rightarrow5\rightarrow7\rightarrow11 的顺序反过来，就会得到这个图：

不难发现这其实就是把 11 所在的这个 Splay 的所有左右儿子翻转过来了。

实现上而言我们肯定不能支持这么大的复杂度开销，打个懒标记翻转 tag 记得下传就行了。

于是我们有了 makert(x) 函数：

void makert(int x)
{
    access(x);Splay(x);
    pushson(x);//打上翻转 tag
}

通过上述两种操作，我们可以得到一种将 x\rightarrow y 的树链信息单拎出来的操作 split(x,y)。

void split(int x,int y)
{
    makert(x);access(y);
    Splay(y);//这里再 Splay 一下是更新信息
}

Link-Cut

接下来就是尽显 LCT 魅力的时刻了，Link-Cut。

如果题目保证 Link 的两端点不连通，Cut 的两端点一定联通，那么这两个操作非常好写。

但是我们还是考虑下一般的普适性的情况，如何判断连通性。

很自然的想到像并查集一样，去找原树根。

那就要实现一个新的函数 findrt(x) 返回 x 所在的树的原树根。

注意到 Splay 的中序遍历是原树从上而下的一条链。

那么我们先 access(x)，接着找出 x 所在 Splay 中序遍历的第一个节点就可以了。

这其实也非常简单，先 Splay(x) 转到当前 Splay 的根然后一直往左儿子走到走不了就找到原树根了。

int findrt(int x)
{
    access(x);Splay(x);
    while(ls) pushdown(x),x=ls;//记得下传 rev tag
    Splay(x);//这个 Splay 把原树根转上去，要不要写取决于你的 Link-Cut 实现方式
    return x;
}

有了 findrt 实现 Link-Cut 就非常简单了，直接放代码：

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);
}

值得注意的是如果你采用猫猫这种先 makert 然后直接判树根的操作需要在上面的 findrt 中最后把原树根转上去，不然就会挂喵。

最后加上你要维护的信息并修改 pushup 函数，我们就完成了一颗 LCT 的实现。

6.3. 应用（板子）

前面的实现讲了之后，这个 LCT 板子是真板子了，这边直接奉上代码。

这里都是一些最基础的维护点权/判断连通性捏/kk。

下面给点基础练习题

P4312 [COI2009] OTOCI

OTOCI - OTOCI

前面是双倍经验捏。

P1505 [国家集训队] 旅游

这题堆码量即可。

P4847 银河英雄传说V2

这题好像是这些题里面最难的，还要再写个 query。

P3950 部落冲突

P2147 [SDOI2008] 洞穴勘测

DYNACON1 - Dynamic Tree Connectivity

这个三个题比板子还简单。

6.3.1.DYNALCA - Dynamic LCA LCT 求 LCA

LCT 是可以求 LCA 的！

那怎么求 LCA 呢？

先对其中的一个点 access（这里假定为 x），这样的话这个点到根的路径都变成了实边。

不难得到的是，x,y 的 LCA 一定在 x 到根的路径上。

所以 x,y 的 LCA 指向 x 的路径已经变成了实边，那么指向 y 的路径就是虚边了。

这个时候我们只需要 access 一下 y，那么在这条路径上的最后一条虚边的父亲即为 LCA。

但是唯一需要注意的是求 LCA 的时候，link 和 cut 不能用 makert 写，不然的话父子关系会变。

附上 代码。

当然，也可以见文章。

P3302 [SDOI2013] 森林

主席树的题，但是要求动态加叶子 LCA，可以用 LCT 也可以用倍增。

6.4. 应用（技巧）

看到这里说明你已经深刻理解（熟读并背诵） LCT 的板子了。

本章节将会讲一些重剖中比较模板的套路或是好题，方式是结合例题分析。

• Warning:从此段开始难度直线上升，至少是紫。

• P.S.：如果找不到锅了可以对下我的出锅合集。

题目讲解排序按照难度不一定单调递增。

那就开始吧：

6.4.0.P3203 [HNOI2010] 弹飞绵羊 轻量化 LCT

这道题算是这个版块中最为简单的了。

首先我们要考虑题意的转化。

P2387 [NOI2014] 魔法森林

维护 MST 的时候记得边权有两个即可。

首先按照第一个边权 a 进行排序，那保证了造出来的树的 a 一定是最小的。

然后对 b 进行动态 MST 维护，每一次删边的时候考虑 a+b 的值的影响，选取更优即可。

附上 代码。

P4234 最小差值生成树

维护边权与 MST 变体的 LCT 捏。

考虑下把边按边权从小到大加进来，那每一次造出环的时候就应该去掉最小边权。

然后如果已成树就最大边权减去最小边权更新答案即可。

附代码 代码。

DYNACON2 - Dynamic Graph Connectivity

详情可以见 SP9576 解题报告。

Best Edge Weight

讲解见文章了，其实我感觉他对于非树上的边就和动态 MST 差不多了。（懒癌不是用 LCT 写的。）

6.4.3.P4319 变化的道路 线段树分治+动态 MST

首先看到这题我们会发现是 MST 的板子，所以我们优先考虑上个 『6.1.1.』 的动态 MST。

然后我们发现了这个美妙傻逼题目的边有存在时间。

• 题目说了每条边只在一个时间段中出现。

所以考虑套一个线段树分治，用线段树维护时间区间上的答案。

每次在符合的时间段里，就把边连上，做完后就断开即可。

附上 代码。

具体分析可以见文章。

P3206 [HNOI2010] 城市建设

注意下线段树分治的 modify 修改的东西要单独存下。

然后和上面那道例题就没区别了。

附上 代码。

6.4.4.P2542 [AHOI2005] 航线规划 LCT 求动态割边/6.4.5.P5622 [DBOI2019] 巫女的职责 LCT 求动态割点

首先是 6.4.4.P2542 [AHOI2005] 航线规划。

发现是删边操作，发现不太好处理，所以考虑和前面一样离线倒序加边。

考虑先缩个点，把每个点双缩成一个点。

那么查询的时候就是链长度 -1（为什么是这样请读者自行推敲一二。）

然后好像就做完了？

但不全然，缩完点之后记得 access 中要写成缩点后的点编号！

附上 代码。（我卡了 2 页，第一页是写挂了，第二页卡最优解，目前是最优解。）

如果怀疑自己 UB 强烈推荐 CF 的自定义评测。

然后是 6.4.5.P5622 [DBOI2019] 巫女的职责。

可以见题解捏。

题意简述：

1.x,y 间连边。 2.单点修改权值。 3.求 x\rightarrow y 上的割点权值和。

前两个操作都很好理解，重点在第三种操作上。

第三种操作的主要难点就在于如何动态求割点了。

首先我们考虑下之前静态求割点是怎么做的。

考虑建一颗圆方树，然后在圆方树上维护即可。

那怎么动态呢？

其实很简单，我们只需要在连边前，判断这两个点是否连通，如果已经连通了，那连上这条边就会产生一个环，也就是点双，给路径上的边全部断开然后直接建圆方树即可。

这个复杂度是正确的。

下面给个略证：

因为只有加边操作，所以任意一个点最多只会被合并一次（因为合并完后就成一个点了） 那这样的话复杂度就是 O(n)，再加上 LCT 本身单点修改复杂度为 \log n，所以均摊后还是 \log n。 证毕。

然后就变成圆方树上查询树链信息了。

附上 代码（卡了下卡到最优解第二了）。

P5489 EntropyIncreaser 与 动态图

就是动态求割点和动态求割边一起放进来了。

很好的一道练手题。

详情见题解了。

我个人采取的方式是封装两个 namespace 做。

P10657 BZOJ4998 星球联盟

边双，也算比较简单的题。

详情见题解。

6.4.6.P4219 [BJOI2014] 大融合 LCT 维护子树信息

知周所众的是，LCT 并不擅长维护子树信息。

但是这道题需要维护动态树的子树信息。

那怎么办呢？

考虑下 LCT 为什么不能维护子树信息。

这一点是因为 LCT 中的父子关系并不确定。

也就是对于一个节点 x，对于他的实子树，肯定都是统计了的。

但是他的虚子树并没有统计进去。

所以我们考虑维护一个 si2 数组即可。

这里给出定义：

比如这道题，就是权值和。

那么在 pushup 函数中，我们就要额外更新下这个数组。

除此之外，还有 access 中我们修改了一个实儿子为虚儿子，所以也要修改下。

最后还有 link 操作的额外增加。

这样就完美解决了。

附 代码。

P.S.: link 时一定要注意，makeroot 要两次。

CF1681F 有很多种做法。

具体做法可以看 CF1681F 解题报告（杂题选做）。

6.4.7.P4271 [USACO18FEB] New Barns P LCT 维护直径

因为题目中有动态加边操作，形态也是森林，所以直接考虑使用 LCT。

是否在同一颗树中考虑使用并查集解决，那么剩下的问题就是如何求这颗树中离 k 最远的点了。

考虑离他最远的点肯定是树的直径的两个端点之一，题意就变成了 LCT 维护直径。

那么新加一个点的时候，考虑加上原本直径的两个点，一共三个点，两两求个距离取最大即可。

代码见题解了。

7. 资料来源鸣谢

部分图片及资料参考 OI Wiki 树链剖分，OI Wiki Splay 树 以及 OI Wiki Link Cut Tree。

部分解法参考 lzyqwq 的题解。

部分长剖解法及图片参考 Ynoi 的博客。

长剖板子中的图来自于 b6e0_ 的博客。