link-cut tree

· · 个人记录

\color{cyan}If$ $\color{cyan}it$ $\color{cyan}weren't$ $\color{cyan}for$ $\color{cyan}learning$ $\color{cyan}link-cut$ $\color{cyan}tree,\color{cyan}I$ $\color{cyan}wouldn't$ $\color{cyan}have$ $\color{cyan}learned$ $\color{cyan}splay$ $\color{cyan}in$ $\color{cyan}my$ $\color{red}lifetime.

我曾经说过这么一句话： 要不是为了学LCT，我这辈子都不会学splay。

现在好了，splay学的差不多，开始学LCT时：

第一眼：什么鬼

第二眼：爆炸

第三眼：不会

第四眼：题解曰：“因为要维护动态链表，所以考虑平衡树维护，理论上splay和fhq treap都是可以的。”

理论上splay和fhq treap都是可以的

理论上splay和fhq treap都是可以的

理论上splay和fhq treap都是可以的

第五眼：不会

第无数眼：放弃

学习笔记-LCT篇·完

upd 2023.12.2

我—会—了一点点。

\color{purple}LCT 强上天，从根强到实虚边。

skr~

请看题：

【模板】动态树（LCT）

题目描述

给定 n 个点以及每个点的权值，要你处理接下来的 m 个操作。
操作有四种，操作从 0 到 3 编号。点从 1 到 n 编号。

数据规模与约定

对于全部的测试点，保证：

开始扯淡：

我们先抛开连边断边：

众所周知，静态树（这里指树的结构不会变化的树）的树链剖分大多数是重链剖分，它的中心思想是把树按照重轻边剖成若干条链（默认你会重链剖分，所以讲的粗略一点）。

而我们的LCT使用的叫做实链剖分，它用一种十分玄学的方式剖链，每次查询就把两点之间的路径变成一条链（这种链就叫实链），在变的过程中链维护链中需要的信息。变完之后链上的信息即为查询的答案。

那么链怎么变呢？

你在想什么？大声的说出来：

链表！

啊不是，噔

文艺平衡树！

对喽，就是文艺平衡树。我们可以用美丽如花的fhq-treap和丑如泥巴的splay。

为什么只能用它们？？

Because they need to split and merge.（英语十级）

为什么要分裂合并？

Please look at 下文.（梅开二度）

我们用多个fhq-treap维护每一条链，并且每条链中序遍历下来每个点深度单调递增，并且对于每条链把fhq中排名为1的节点的成员变量.to设为原树中链顶的点的父亲，即虚边，并且fhq中每个节点维护成员变量.sum为fhq中此点子树中所有点点权的异或和。

假设树是这样的：

[图片]

每条链是这样的：

[图片]

连完父亲是这样的：

[图片]

基本的讲完了，接着讲主要的。

link(x,y)

则有几个前置函数需要讲解： - $find(x)$表示$x$所在**树（是原树，而非fhq-treap）** 的根节点。 - $makeroot(x)$表示让$x$成为$x$**树**中的根。 那么我们先让 $x$ 当根，然后让 $x$ 认 $y$ 为父亲即可（指原树中的父亲，并非fhq中的父亲）。 则有： ```cpp void link(int x,int y) { if(find(x)==find(y))//在同一棵树里面，再连就有环了 return; makeroot(x);//x成为根 to(x)=y;//x为根节点，则x所在的链中x一定为排名为1的点 return; } ``` ## $cut(x,y)

接着上面的思路，要切断 x 和 y之间的边，要判find(x)是否等于find(y)。若不等于，那删你癌慕啊。

    if(find(x)!=find(y))
        return;

又来几个函数：

[图片]

那么我们先让 x 当根，然后 y与x之间变为实链。然后让x和x变成实链，那么原本 x连向y的那条边就会肾虚，即x到y的链，但是切掉了x。

[图片]

那么只需要看y树中排名为1的数是否为y，如果是，说明x和y直接连边，否则删你癌慕直接return啊。

void cut(int x,int y)
{
    if(find(x)!=find(y))//无边可删
        return;
    makeroot(x);
    access(y);
    access(x);
    if(front(y)==y)//保证y是第一名，不然x和y中间还会有小三（bushi
        to(y)=0;//切断关系
}

query(x,y)

求原树中 x 到 y 路径中所有点点权异或之和。

实现：

滑稽吧，这么简单还需要讲

首先让 x 当根，然后直接返回节点 access(y) 的.sum就好啦。

int query(int x,int y)
{
    makeroot(x);
    return tree[access(y)].sum;
}

update(x,val)

将点 x 的点权改为 val

滑稽吧

先让 x 当根，再 access(x)，此时就能把 x 单独分离出来，然后直接修改就可以拉。

void update(int x,int val)
{
    makeroot(x);//x当根
    access(x);//x与x成链，将x单独分离
    tree[x].val=tree[x].sum=val;//直直直直直直直接修改
}

那么所有的操作我们就全部解决了ヽ(°▽ﾟ)ノ

那么……

How do we write them:

makeroot$、$access$、$front$、$find

莫得关系，逐一攻破：

NO.1 access(x)

作用前文讲过，这里不再赘述。

首先，定义一个空fhq，把每个处理完的链一个个合并，最后得到[维护(根到 x 的链)的fhq]的根节点（防止你们误解括号都打上了）

得到伪代码：

int access(int cur)
{
    int root=0;
    从x开始跳链，保证x不跳到根节点的爸爸（0节点）
    {
        把链分成不比x低的链和比x低的链;
        合并刚刚的链和root;
        x=root所在树的排名为1的节点的.to，即原树中root所在树的排名为1的节点的爸爸;
    }
    return root;
}

即

[图片]

再次引进两个函数：

重点是 $split$： ## 1.1 按点分裂 即把fhq分成两部分：[1,参数的排名]和[参数的排名+1,树的大小] [图片]