题解：P3384 【模板】重链剖分 / 树链剖分

yangzichen1203 · 2026-01-19 16:30:32 · 算法·理论

本来是写给树链剖分模板的，以诈骗新手，但没人审，所以申请全站推荐。

这是一篇单 \log 的题解

参考资料：

https://negiizhao.blog.uoj.ac/blog/4912

https://www.cnblogs.com/laijinyi/p/18373391/Top-Tree-1

https://www.luogu.com.cn/article/42ajqoux

https://www.cnblogs.com/Richardwhr/p/18834468

https://oi.wiki/ds/top-tree/

前言（与后文无关）

首先考虑一个问题：我们如何表示一棵树？

最简单的方法显然用点和边表示，但这种方式不利于我们进行动态树操作，所以我们来考虑下面这种树的表示法。

首先定义簇（cluster）：簇是一个边的集合，满足最多只有两个界点与其他簇相邻，一般我们称深度小的界点为上界点，深度大的界点为下界点。

每一条边显然都是一个簇，我们称为基簇（base cluster）；而所有边显然也是一个簇，我们称为根簇（root cluster）。那么我们就可以把基簇通过一些合并操作变成根簇，然后通过记录合并的顺序来记录整颗树的信息。

考虑 Rake 和 Compress 两个操作合并簇，一个 Compress 操作可以消除一个度为 2 的点，一个 Rake 操作可以消除一个度为 1 的点。（如图） 由于 Rake 和 Compress 操作都是二元操作，所有我们可以用一棵二叉树来表示整个合并的过程，我们称为 Top Tree。问题就转化为了如何维护这棵 Top Tree。（左图为合并的过程，右图为 Top Tree（圆点为 Rake 节点，方点为 Compress 节点））

我们可以 O(n) 建出一棵静态 Top Tree，并用一些方法把树高控制在 O(\log n)，所以我们就可以在 O(\log n) 的时间内单边修改，全局查询，我们就可以解决如动态直径、树上 DDP 等问题。

但这种方法具有局限性：它只支持单边修改，不支持链修改，子树修改。所以我们需要一种更高级的方法来维护。

SATT 是什么

SATT（Self-Adjusting Top Tree），是最强大的动态树，它支持高效的动态树操作，路径操作，子树操作。

Warning：SATT 是基于点的，Top Tree 是基于边的，所以 SATT 其实更类似于 LCT 而不是 Top Tree。

对于一棵树分层定根，每一层选一条到根链，建一棵 BST 维护 Compress 操作的顺序，我们称为 Compress Tree，其节点称为 Compress Node。对于每一个节点，可能有多个簇要 Rake 上去，我们让它们先互相 Rake，变成一个簇后再 Rake 上去，建一棵 BST 维护 Rake 操作的顺序，我们称为 Rake Tree，其节点称为 Rake Node。

我们可以认为 SATT 就是把 LCT 的所有虚儿子存储在 Rake Tree 上来做到高效子树操作。

发现 Compress Tree 和 Rake Tree 此时是相互独立的，所以考虑如何把它们结合到一起。我们把 Rake Tree 的根节点连到 Compress Node 的中儿子上，把 Compress Tree 的根节点连到 Rake Node 的中儿子上。由于 Rake Tree 表示合并顺序，而 Compress Tree 表示实际的点的顺序，所以 Compress Node 不一定有中儿子，而 Rake Node 一定要有中儿子。

下面是我自己画的图。

原树（粗边表示实链）：

一种可能的 SATT 形态（单字母点表示 Compress Node，双字母点表示 Rake Node）：

如何维护 SATT

我们一般使用 Splay 来维护整棵 SATT，来保证均摊复杂度为单 \log。

需要维护的信息：

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<=k;i++)
#define dFor(i,j,k) for(int i=j;i>=k;i--)
using namespace std;
#define MAXN 100005
#define ls son[0]
#define rs son[1]
#define ms son[2]
#define endl '\n'
int n,m,rt,p;
int st[MAXN*2],top=0,tot=0;
struct Data{
    int sz,sum;
    Data(int _sz=0,int _sum=0){
        sz=_sz;sum=_sum;
    }
};
Data operator +(Data x,int y){
    return Data(x.sz,(x.sum+1ll*y*x.sz%p)%p);
}
Data operator +(Data x,Data y){
    return Data((x.sz+y.sz)%p,(x.sum+y.sum)%p);
}
struct Node{
    int son[3],val,fa,right,left;
    bool rev;
    int pathadd,treeadd;
    Data path,tree;
    void clear(){
        ls=0;rs=0;ms=0;val=0;fa=0;right=0;left=0;rev=0;pathadd=0;treeadd=0;
        path=tree=Data();
    }
}tr[MAXN*2];

需要实现的函数：基本于 LCT 相同。