LCT 的学习建议

• LCT 一类的算法虽然不在考纲内，但是并非没用。比如考场上遇到弹飞绵羊，又想不到分块，LCT 就是不二的选择。
• LCT 等模板的调试：很吃熟练度，多写，一遍写对。
• 学新算法的时候直接跟着别人的，不用自己写。选择别人的优质模板（优美、常数小）。
• 有一类特别的不换根 LCT，建议作为特化的模板记忆，类似于序列上的并查集和并查集的关系。甚至隔壁的维护 DFS 序的块状链表也可以看作特化的模板。

LCT - Link Cut Tree

P3690 【模板】动态树（LCT）

LCT 用于做一些动态树问题，即维护一个森林并支持一些加边删边操作（而且保持是森林）。

参考：

• OI Wiki 的 LCT
• 严格鸽 的 LCT（不得不说鸽鸽的码风是真的好！）
• 2022 WC 的讲解

实链剖分

对于森林上一个节点，我们任意选取它的一个儿子作为实儿子（也可以不选），在他们之间连一条实边，在这个点和其他儿子之间连虚边。显然这样的剖分和重链剖分一样会产生很多由实边组成的实链。在后续的操作中我们会用 Splay 来维护这些实链。

正是因为实儿子可以任意选取，我们可以按需调整实链剖分的具体样子。

辅助树（Auxiliary Tree）

（左图：原树；右图：辅助树）

对于原树的每一个实链，我们使用一个 Splay 维护：Splay 的中序遍历为实链从上到下的顺序。

这些 Splay 也不是独立的，我们用原树上的虚边将这些 Splay 串起来。具体来说，对于原树上的一条虚边 $son \to fa$，我们找到 $son$ 所在的 Splay 的根 $rt$，在辅助树上连虚边 $rt \to fa$。

不难发现我们现在通过新的虚边将这些 Splay 串成了一整棵树，即辅助树。

注意，辅助树的实边和原树的实边没有一一对应的关系，例如上图中原树 $G \leftrightarrow H$ 这条实边就不存在于辅助树中。

实边和虚边在代码中的体现：

• 对于实边，儿子认父亲，父亲认儿子。
• 对于虚边，儿子认父亲，父亲不认儿子。

因为虚边的存在，辅助树不是二叉树。但是若只看实边，辅助树是二叉树森林，所以我们依然会用”左儿子”“右儿子”这种说法。

重写基础工具包

bool isroot(int u) { // u 是不是当前 Splay 的根
    return tr[fa[u]][0] != u && tr[fa[u]][1] != u;
}
void rotate(int u) {
    int v = fa[u], w = fa[v];
    bool r = dir(u);

    tr[v][r] = tr[u][!r];
    tr[u][!r] = v;
    if (!isroot(v)) tr[w][dir(v)] = u; // Here

    if (tr[v][r]) fa[tr[v][r]] = v;
    fa[v] = u;
    fa[u] = w;

    pushup(v), pushup(u);
}
void update(int u) {
    if (!isroot(u))
        update(fa[u]);
    pushdown(u);
}
void splay(int u) {
    update(u);
    while (!isroot(u)) { // Here
        int v = fa[u];
        if (!isroot(v)) // Here
            rotate(dir(u) == dir(v) ? v : u);
        rotate(u);
    }
}

LCT 核心操作：access

这个操作的地位就类似于 Splay 中的 splay，接下来的一切其他操作围绕它展开，同时也是这个操作保证了 LCT 仅有 1log 的时间复杂度。

access(u) 代表让 $u$ 与原树根节点在同一条实链上，且 $u$ 是实链底部。

void access(int u) {
    for (int v = 0; u; v = u, u = fa[u]) {
        splay(u);
        tr[u][1] = v;
        // 把右儿子从实边变虚边
        // 因为要保证原树上没有实儿子，右儿子代表的是深度大的点
        // 同时把上一次操作的点 v 接到右儿子，因为上一次操作的点肯定深度大
        pushup(u);
    }
}

根据 OI-Wiki，$n$ 个点执行 $m$ 次 access 的复杂度是 $O((n+m) \log n)$。也就是说均摊下来是 $\log$ 的。这句话是直接从上面 splay 复制过来的

makeroot

makeroot(u) 代表把 $u$ 作为原树的新根节点，即平常说的换根。

我们可以先 access(u)，然后把 $u$ 所在的整条实链翻转（需要一个支持翻转的 Splay）。

void makeroot(int u) {
    access(u);
    splay(u);
    maketag(u);
}

findroot

findroot(u) 代表查找 $u$ 所在原树的根节点。

先 access(u)，然后把 $u$ splay 上去之后一路往左走，就可以找到深度最小的节点。找到之后要 splay 上去。

int findroot(int u) {
    access(u);
    splay(u);
    while (tr[u][0])
        u = tr[u][0];
    splay(u);
    return u;
}

split

split(u, v) 把 $u$ 和 $v$ 之间的路径弄成一条实链。并且在这之后 $u$ 是原树的根，$v$ 是 Splay 的根。

void split(int u, int v) {
    makeroot(u);
    access(v);
    splay(v);
}

link & cut

link(u, v) 在 $u$ 和 $v$ 之间连轻边即可。注意 $u$ 和 $v$ 原先不能在同一棵树上。

cut(u, v) 也好办，我们尝试把 $u \leftrightsquigarrow v$ 这条路径拿出来并且以 $v$ 为 Splay 根，如果拿完之后 $u$ 是 $v$ 的左儿子，且 $u$ 没有右儿子，说明这条边存在，完全删掉即可。

bool link(int u, int v) {
    if (findroot(u) == findroot(v))
        return false;
    makeroot(u);
    fa[u] = v;
    return true;
}
bool cut(int u, int v) {
    split(u, v);
    if (tr[v][0] != u  || tr[u][1])
        return false;
    tr[v][0] = 0, fa[u] = 0;
    return true;
}

如果能够保证边存在，那么去掉两个 if 判断即可。

LCT 维护子树信息

见 “共价大爷游长沙” 一题。

💡LCT 撤销

虽然 LCT 是均摊复杂度，但是它可以支持带撤销的东西，比如线段树合并。因为各种操作都有对应的相反操作，共享势能。例题：P4319 变化的道路，做法类似下面例题的魔法森林。

不换根 LCT

TODO:

LCT 例题

课后作业 1 - P3203 [HNOI2010] 弹飞绵羊 (Easy)

有 $n$ 个点，每个点有一个系数 $a_i$，你处于位置 $i$ 可以走到 $i+a_i$，若 $i+a_i>n$ 则你走出了地图。现 $m$ 个操作有两种：1、把 $a_j$ 修改为 $k$。2、询问你位于点 $j$ 时，需要走多少步走出地图。$n \le 2 \times 10^5, m \le 10^5$。

首先发现整个玩意儿就是一个树（给”跳出”加一个虚拟的点 $n+1$），修改操作相当于 link & cut，所以非常自然想到 LCT。

询问也很简单，把 $j \leftrightsquigarrow n+1$ 这条路径拉出来，以 $j$ 为 Splay 根，查询 $j$ 在 Splay 上的子树大小 $-1$ 即可。

实现也是超级简单的：把所有点 $siz$ 初始化成 $1$，每次 pushup 里面更新就可以了。

P2387 [NOI2014] 魔法森林 (Normal)

类似题目：P4172 [WC2006] 水管局长

给定 $n$ 个点 $m$ 条边的无向图，每条边有两个权值 $a$ 与 $b$。求一条 $1$ 到 $n$ 的路径使得路径经过边的最大 $a$ 与最大 $b$ 的和最小。无法到达输出 $-1$。 $n \le 5 \times 10^4, m \le 10^5$。

“$2$ 个权值” 这个条件有说法。我们不妨考虑一档自己造的部分分，所有 $b$ 都相等即只要考虑 $a$，立刻就能想到把所有边按 $a$ 排序之后依次加边的思路。

现在只多了一个权值，我们可以依然沿用刚才的思路，把所有边按 $a$ 排序后依次加边，但是用一些数据结构维护 $b$。我们需要在加边的同时维护 $1 \leftrightsquigarrow n$ 的最大值的最小值。

如果感觉这个过程有点像 Kruskal 那就对了，因为最小生成树就是满足任意 $u \leftrightsquigarrow v$ 上最大值最小的结构（这个东西叫最小瓶颈路）。我们考虑怎么在加边的同时维护 $b$ 的最小生成森林。

考虑如果这张图原先是森林，当 $u \leftrightarrow v$ 这条边被加入时不是森林了，我们应该怎么让它变回森林。不难发现，我们只要把含有 $u,v$ 的这个环上的最大边删掉即可，当然最大边是 $u \leftrightarrow v$ 自己的情况要特判。

我们需要一个支持 加边 + 查询树链最大值 的结构，不难想到 LCT。

Trick LCT 维护边权，可以直接建虚点，将虚点点权设为这个边权。

* 既然说到瓶颈相关的问题了，再补充一个结论：最小生成树一定是最小瓶颈生成树（充分非必要）。

#207. 共价大爷游长沙 (Hard)

有一棵树，会改变它的形态（每次操作删除一条边再加入一条边，保证依旧是棵树）。 有一个路径集合，初始为空，路径集合会被更改（每次操作加入一个点对 $(x,y)$ 表示路径，或者删去一个点对）。 询问操作是询问一条边是否被路径集合的所有路径经过。 $n \le 10^5$。

首先这个题一股浓浓的随机化味道。

考虑怎么刻画”边在路径上”。一开始我尝试用 $\text{dis}$ 刻画，但是显然是不现实的。

Trick 在树上，如果边 $u \leftrightarrow v$ 属于树链 $x \leftrightsquigarrow y$，那么以 $u$ 为根的话，$v$ 的子树中只能有 $x$ 和 $y$ 中的一个。

有了这个从天而降的思路之后就非常简单了：给每组 $x$ 和 $y$ 赋相同随机权，把 $u$ 作为根求 $v$ 的子树异或和，如果这个异或和等于全部路径的权值异或和那么就大概率是 Yes，不等于则一定是 No。

这个东西就可以直接用 LCT 维护了。

LCT 维护子树信息

我们尝试使用 LCT 维护子树异或和。

开三个数组 val、siz、sizv 分别代表节点本身的权值、节点在辅助树上的子树异或和、节点在辅助树上的所有虚子树异或和。注意，siz 包含节点自身，sizv 不包含。

具体来说，有关系：siz[u] = val[u] ^ siz[tr[u][0]] ^ siz[tr[u][1]] ^ sizv[u];。

我们要在每次出现虚实切换的时候维护好 sizv，并 pushup 同步到 siz。包含虚实切换操作的有 access 和 link 两个操作。

查询 $u$ 原树子树信息的时候，如果 $u$ 在辅助树上有实儿子，那么不能保证一定在其右边，所以直接查 siz 是不对的。但是，只要没有实儿子就是对的，因此我们把 $u$ 到 $v$ 单独拎出来，以 $v$ 为辅助树根，此时 siz[u] 就确确实实是原树上 $u$ 的子树异或和。

接下来给出这题的实现：

（注：因为异或的逆运算是自身，所以用”加”和”减”的注释代表是加上贡献还是去掉贡献。据此也可以发现一点，LCT 维护子树信息必须要有可减性）

Val val[MAXN], siz[MAXN] /*子树异或和*/, sizv[MAXN] /*虚子树异或和*/;

void pushup(int u) {
    siz[u] = val[u] ^ siz[tr[u][0]] ^ siz[tr[u][1]] ^ sizv[u];
}

void access(int u) {
    for (int v = 0; u; v = u, u = fa[u]) {
        splay(u);
        sizv[u] ^= siz[tr[u][1]]; // 加
        tr[u][1] = v;
        sizv[u] ^= siz[v]; // 减
        pushup(u);
    }
}

void link(int u, int v) {
    makeroot(u);
    fa[u] = v;
    // 先把 v 弄到辅助树的根才能直接修改 sizv
    access(v); splay(v);
    sizv[v] ^= siz[u]; // 加
    pushup(v);
}
void cut(int u, int v) {
    split(u, v);
    tr[v][0] = 0, fa[u] = 0;
    pushup(v);
}
void update_xor(int u, Val k) {
    // 先把 u 弄到辅助树的根才能直接修改 val
    access(u); splay(u);
    val[u] ^= k;
    pushup(u);
}
Val query(int u, int v) {
    split(u, v);
    return siz[u];
}

注：在其他人的题解中可能会出现非常匪夷所思的一种写法——在 link 中使用 split(u, v)，语义完全不 make sense。但是能够发现，其实就是把 makeroot(u); access(v); splay(v); 三个操作合在了一起，理论上是正确的。我觉得这种写法很莫名其妙，但是很多人都在使用，所以值得一提。

参考：

• 官方题解：《共价大爷游长沙》解题报告
• 「题解」UOJ 207. 共价大爷游长沙
• UOJ #207. 共价大爷游长沙（LCT + 异或哈希)（码风超级好的野生题解！）

P4299 首都 (Normal)

一开始有 $n$ 个结点，没有边。有三种操作：

• 将两个结点间连一条边，并且保证两个结点属不同连通块。
• 询问一个连通块中的重心。（有多个选择编号最小的）
• 询问所有连通块中重心编号的异或和。

$n \le 10^5$。

回顾一下 重心的性质 OI-Wiki：

• 树中所有点到某个点的距离和中，到重心的距离和是最小的。
• 一棵树有 $1$ 个或 $2$ 个重心。若有 $2$ 个重心，则它们相邻。
• 以树的重心为根时，所有子树中最大子树的大小最小，且不超过整棵树大小的一半。
• 把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。
  • 在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

考虑启发式合并，每次连边的时候，把小的树拆开，一个一个点往大树上连。根据最后一条性质，重心最多只移动一条边，也就是说时间复杂度是 $O(\lvert T \rvert)$ 的，其中 $T$ 是小树。

判断大树重心要不要动，需要维护支持换根的子树大小查询。使用 LCT 即可。

时间复杂度 $O(n \log^2 n)$。启发式合并 1log，LCT 1log。

当然 2log 肯定不是最优的，题解区有 Splay 二分的 1log 做法。

P3348 [ZJOI2016] 大森林 (Lunatic)

WTF。

TODO: