LinkCutTree　学习笔记

参考来源

https://www.zybuluo.com/xzyxzy/note/1027479

https://www.cnblogs.com/zhoushuyu/p/8137553.html

目的&作用

树的动态加边/删边

维护两点联通性, 树链信息, 生成树等

前提

应为无根树可以随意钦点树根, \(Splay\)树也同样

所以下面的算法都基于从根连出去的树链形成的\(Splay\)树, 以及换根, 等等操作

详解

Splay以什么为关键值?以什么为下标?

以深度为关键值(不用具体存储, 用二叉查找树表示相对关系)

以原树中编号为下标

实边和虚边

每一条由实边形成的树链由一个\(Splay\)维护
每个点至多有一条连向其儿子的实边
一个原树会被划分为多块\(Splay\)

父与子

假设\(ch[x][0/1]\)代表在\(Splay\)中\(x\)节点的左右儿子, \(fa[x]\)为父亲

在原树中与\(x\)虚边连接的节点就不会出现在\(Splay\)树的父子中
一个\(Splay\)的\(root\)的\(fa\)连向原树中该实链链顶的父亲(特例), 而父亲没有这个儿子(显然)
- 由此可区分\(root\)和其他点

bool isroot(int x)
{
    return ch[fa[x]][0] != x && ch[fa[x]][1] != x;
}

这样就不记录\(root\)了

正是因为\(root\)会连接两个不同的\(Splay\), 所以在\(LCT\)中要特别注意边界问题, 在rotate()和splay()等中都会涉及

`access(x)`

将树根到\(x\)的路径串在一个\(Splay\)中, 并修改相关实边虚边

由于\(Splay\)的根是连向其他\(Splay\)的出口, 而实链链顶的父亲(\(fa[root]\))则是另一个\(Splay\)的入口, 我们主要关注这种节点, 还有\(x\)点

发现将\(root\)和\(fa[root]\)改实边后, \(fa[root]\)的实边就要断开, 而该实儿子是\(ch[][1]\)(深度较大)
切换虚实边只要\(ch[fa[root]][1]=root\)即可, 一步到位

我们能保证\(root\)刚被包含在根到\(x\)的路径上, 即新的\(Splay\)分区中(见makeroot), (但是为了保证复杂度?), 一开始将\(x\)splay到根, 之后则选择\(fa[root]\), 即\(fa[x]\)splay到根

还有, splay改变了树的形态, 而splay的路径上的点可以在rotate的时候pushup掉, 那么还剩下根刚好没有pushup, 单独做一下即可(pushup(fa[x])时会把\(x\)统计上去, 不用担心新实边上的上传)

总结一下代码就是这样

void access(int x)
{
    for (int y = 0; x; y = x, x = fa[x])
        splay(x), ch[x][1] = y, pushup(x);
}

基于`access()`的一些操作

`makeroot()`

原树换根，用处看下面一些函数就知道了

先access(x)

发现现在已经把\(root --> x\)抓起来了，而\(x\)在最深处

于是splay(x)　+　reverse(x)就可以了(想想为什么?)

void makeroot(int x)
{
    access(x); splay(x);
    reverse(x);
}

`findroot()`

看代码

int findroot(int x)
{
    access(x); splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
}

`link(x, y)`

void link(int x, int y)
{
    if (findroot(x) == findroot(y)) return ;
    makeroot(x);
    fa[x] = y;　//x整棵树接到y下面
}

`split(x, y)`和`cut(x, y)`

可以随便换根的

看代码，想想为什么?

void split(int x, int y)
{
    makeroot(x);
    access(y); splay(y);
}
void cut(int x, int y)
{
    makeroot(x);
    if (findroot(y) != x || fa[y] != x) return ;　// 想想为什么?
    split(x, y);
    fa[x] = ch[y][0] = 0;
    pushup(y);
}

`rotate()`和`splay(x)`

将splay的路径上从上到下先pushdown()

void rotate(int x)
{
    int y = fa[x], z = fa[y];
    int zy = (y == ch[z][1]), yx = (x == ch[y][1]);
    if (!isroot(y)) ch[z][zy] = x;
    fa[x] = z; // fa
    ch[y][yx] = ch[x][yx ^ 1], fa[ch[x][yx ^ 1]] = y;
    ch[x][yx ^ 1] = y; fa[y] = x;
    pushup(y); pushup(x);
}
void splay(int x) // x --> root
{
    if (!x) return ;
    stk[top = 1] = x;
    for (int tmp = x; !isroot(tmp); tmp = fa[tmp]) stk[++ top] = fa[tmp];
    while (top) pushdown(stk[top --]);
    while (!isroot(x))
    {
        int y = fa[x], z = fa[y];
        int zy = (y == ch[z][1]), yx = (x == ch[y][1]);
        if (!isroot(y))
            (zy == yx) ? rotate(y) : rotate(x);
        rotate(x);
    }
    pushup(x);
}

后续见例题，基础代码见模板题

带修改判断两点联通性
带修改查询路径异或和

例题

BZOJ2049: Sdoi2008Cave 洞穴勘测

树, 三种操作，连边, 删边(保证存在), 查询连通性

模板Link Cut Tree(动态树)

树, 四种操作, 查询路径上异或和, 连边(要求已联通则不连), 删边(不保证联通), 修改点权

修改点权：把根换成他，这样单点修改他就行了，影响之后要用的时候自然会算到

查询：split出来，完事

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long LL;
const int MAXN = 3e5 + 10;

inline LL in()
{
    LL x = 0, flag = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return x * flag;
}

int n, m;

int fa[MAXN], ch[MAXN][2], rev[MAXN];
LL val[MAXN], sum[MAXN];
int top, stk[MAXN];

void reverse(int x)
{
    if (!x) return;
    swap(ch[x][0], ch[x][1]);
    rev[x] ^= 1;
}
void pushup(int x)
{
    sum[x] = sum[ch[x][0]] ^ sum[ch[x][1]] ^ val[x];
}
void pushdown(int x)
{
    if (!rev[x]) return;
    reverse(ch[x][0]); reverse(ch[x][1]);
    rev[x] = 0;
}
bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
void rotate(int x)
{
    int y = fa[x], z = fa[y];
    int zy = (y == ch[z][1]), yx = (x == ch[y][1]);
    if (!isroot(y)) ch[z][zy] = x;
    fa[x] = z; // fa
    ch[y][yx] = ch[x][yx ^ 1], fa[ch[x][yx ^ 1]] = y;
    ch[x][yx ^ 1] = y; fa[y] = x;
    pushup(y); pushup(x);
}
void splay(int x) // x --> root
{
    if (!x) return ;
    stk[top = 1] = x;
    for (int tmp = x; !isroot(tmp); tmp = fa[tmp]) stk[++ top] = fa[tmp];
    while (top) pushdown(stk[top --]);
    while (!isroot(x))
    {
        int y = fa[x], z = fa[y];
        int zy = (y == ch[z][1]), yx = (x == ch[y][1]);
        if (!isroot(y))
            (zy == yx) ? rotate(y) : rotate(x);
        rotate(x);
    }
    pushup(x);
}

void access(int x)
{
    for (int y = 0; x; y = x, x = fa[x])
        splay(x), ch[x][1] = y, pushup(x);
}
void makeroot(int x)
{
    access(x); splay(x);
    reverse(x);
}
int findroot(int x)
{
    access(x); splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
}
void link(int x, int y)
{
    if (findroot(x) == findroot(y)) return ;
    makeroot(x);
    fa[x] = y;
}
void split(int x, int y)
{
    makeroot(x);
    access(y); splay(y);
}
void cut(int x, int y)
{
    makeroot(x);
    if (findroot(y) != x || fa[y] != x) return ;
    split(x, y);
    fa[x] = ch[y][0] = 0;
    pushup(y);
}
LL query(int x, int y)
{
    split(x, y);
    return sum[y];
}
void modify(int x, LL y)
{
    access(x); splay(x);
    val[x] = y;
    pushup(x);
}

int main()
{
    n = in(), m = in();
    for (int i = 1; i <= n; ++ i) val[i] = in();
    while (m --)
    {
        int opt = in(), x = in(); LL y = in();
        if (opt == 0) printf("%lld\n", query(x, y));
        else if (opt == 1) link(x, y);
        else if (opt == 2) cut(x, y);
        else if (opt == 3) modify(x, y);
    }
    return 0;
}

WC2006水管局长

https://www.lydsy.com/JudgeOnline/problem.php?id=2594

https://www.luogu.org/problemnew/show/P4172

实边