Link Cut Tree

简介

Link/Cut Tree 是一种数据结构，我们用它来解决 动态树问题。

Link/Cut Tree 又称 Link-Cut Tree，简称 LCT，但它不叫动态树，动态树是指一类问题。

Splay Tree 是 LCT 的基础，但是 LCT 用的 Splay Tree 和普通的 Splay 在细节处不太一样（进行了一些扩展）。

问题引入

维护一棵树，支持如下操作：

修改两点间路径权值。
查询两点间路径权值和。
修改某点子树权值。
查询某点子树权值和。

这是一道树剖模版题。

但是再加一个操作：

断开并连接一些边，保证仍是一棵树。

要求在线求出上面的答案。

这就成了动态树问题，可以使用 LCT 求解。

动态树问题

维护一个森林，支持删除某条边，加入某条边，并保证加边，删边之后仍是森林。我们要维护这个森林的一些信息。

一般的操作有两点连通性，两点路径权值和，连接两点和切断某条边、修改信息等。

从 LCT 的角度回顾一下树链剖分

对整棵树按子树大小进行剖分，并重新标号。
我们发现重新标号之后，在树上形成了一些以链为单位的连续区间，并且可以用线段树进行区间操作。

转向动态树问题

我们发现我们刚刚讲的树剖是以子树大小作为划分条件。那我们能不能重定义一种剖分，使它更适应我们的动态树问题呢？

考虑动态树问题需要什么链。

由于动态维护一个森林，显然我们希望这个链是我们指定的链，以便利用来求解。

实链剖分

对于一个点连向它所有儿子的边，我们自己选择一条边进行剖分，我们称被选择的边为实边，其他边则为虚边。对于实边，我们称它所连接的儿子为实儿子。对于一条由实边组成的链，我们同样称之为实链。请记住我们选择实链剖分的最重要的原因：它是我们选择的，灵活且可变。正是它的这种灵活可变性，我们采用 Splay Tree 来维护这些实链。

LCT

我们可以简单的把 LCT 理解成用一些 Splay 来维护动态的树链剖分，以期实现动态树上的区间操作。对于每条实链，我们建一个 Splay 来维护整个链区间的信息。

辅助树

我们先来看一看辅助树的一些性质，再通过一张图实际了解一下辅助树的具体结构。

在本文里，你可以认为一些 Splay 构成了一个辅助树，每棵辅助树维护的是一棵树，一些辅助树构成了 LCT，其维护的是整个森林。

辅助树由多棵 Splay 组成，每棵 Splay 维护原树中的一条路径，且中序遍历这棵 Splay 得到的点序列，从前到后对应原树「从上到下」的一条路径。
原树每个节点与辅助树的 Splay 节点一一对应。
辅助树的各棵 Splay 之间并不是独立的。每棵 Splay 的根节点的父亲节点本应是空，但在 LCT 中每棵 Splay 的根节点的父亲节点指向原树中 这条链 的父亲节点（即链最顶端的点的父亲节点）。这类父亲链接与通常 Splay 的父亲链接区别在于儿子认父亲，而父亲不认儿子，对应原树的一条虚边。因此，每个连通块恰好有一个点的父亲节点为空。
由于辅助树的以上性质，我们维护任何操作都不需要维护原树，辅助树可以在任何情况下拿出一个唯一的原树，我们只需要维护辅助树即可。

现在我们有一棵原树，如图所示。（加粗边是实边，虚线边是虚边。）

tree

由刚刚的定义，辅助树的结构如图所示。

auxtree

考虑原树和辅助树的结构关系

原树中的实链 : 在辅助树中节点都在一棵 Splay 中。
原树中的虚链 : 在辅助树中，子节点所在 Splay 的 Father 指向父节点，但是父节点的两个儿子都不指向子节点。
注意：原树的根不等于辅助树的根。
原树的 Father 指向不等于辅助树的 Father 指向。
辅助树是可以在满足辅助树、Splay 的性质下任意换根的。
虚实链变换可以轻松在辅助树上完成，这也就是实现了动态维护树链剖分。

接下来要用到的变量声明

ch[N][2] 左右儿子
f[N] 父亲指向
sum[N] 路径权值和
val[N] 点权
tag[N] 翻转标记
laz[N] 权值标记
siz[N] 辅助树上子树大小
Other_Vars

函数声明

一般数据结构函数（字面意思）

PushUp(x)
PushDown(x)

Splay 树的函数

下面是 Splay 树中用到的函数，具体可以查阅 Splay 树。

Get(x) 获取 $x$ 是父亲的哪个儿子。
Splay(x) 通过和 Rotate 操作联动实现把 $x$ 旋转到 当前 Splay 的根。
Rotate(x) 将 $x$ 向上旋转一层的操作。

新操作

Access(x) 把从根到 $x$ 的所有点放在一条实链里，使根到 $x$ 成为一条实路径，并且在同一棵 Splay 里。只有此操作是必须实现的，其他操作视题目而实现。
IsRoot(x) 判断 $x$ 是否是所在树的根。
Update(x) 在 Access 操作之后，递归地从上到下 PushDown 更新信息。
MakeRoot(x) 使 $x$ 点成为其所在树的根。
Link(x, y) 在 $x, y$ 两点间连一条边。
Cut(x, y) 把 $x, y$ 两点间边删掉。
Find(x) 找到 $x$ 所在树的根节点编号。
Fix(x, v) 修改 $x$ 的点权为 $v$ 。
Split(x, y) 提取出 $x, y$ 间的路径，方便做区间操作。

宏定义

#define ls ch[p][0]
#define rs ch[p][1]

函数讲解

`PushUp()`

void PushUp(int p) {
  // maintain other variables
  siz[p] = siz[ls] + siz[rs] + 1;
}

`PushDown()`

void PushDown(int p) {
  if (tag[p] != std_tag) {
    // pushdown the tag
    tag[p] = std_tag;
  }
}

`Splay() && Rotate()`

这里 Splay() 和 Rotate() 与 Splay 树的实现有些区别。

#define Get(x) (ch[f[x]][1] == x)

void Rotate(int x) {
  int y = f[x], z = f[y], k = Get(x);
  if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
  // 上面这句一定要写在前面，普通的 Splay 是不用的，因为 isRoot  (后面会讲)
  ch[y][k] = ch[x][!k], f[ch[x][!k]] = y;
  ch[x][!k] = y, f[y] = x, f[x] = z;
  PushUp(y), PushUp(x);
}

void Splay(int x) {
  Update(
      x);  // 马上就能看到啦。在 Splay 之前要把旋转会经过的路径上的点都 PushDown
  for (int fa; fa = f[x], !isRoot(x); Rotate(x)) {
    if (!isRoot(fa)) Rotate(Get(fa) == Get(x) ? fa : x);
  }
}

以上函数可以查阅 Splay 树。

下面是 LCT 独有的函数。

`isRoot()`

// 在前面我们已经说过，LCT 具有 如果一个儿子不是实儿子，他的父亲找不到它的性质
// 所以当一个点既不是它父亲的左儿子，又不是它父亲的右儿子，它就是当前 Splay 的根
#define isRoot(x) (ch[f[x]][0] != x && ch[f[x]][1] != x)

`Access()`

// Access 是 LCT
// 的核心操作，试想我们想求解一条路径，而这条路径恰好就是我们当前的一棵 Splay，
// 直接调用其信息即可。先来看一下代码，再结合图来看看过程
int Access(int x) {
  int p;
  for (p = 0; x; p = x, x = f[x]) {
    Splay(x), ch[x][1] = p, PushUp(x);
  }
  return p;
}

我们有这样一棵树，实线为实边，虚线为虚边。
它的辅助树可能长成这样（构图方式不同可能 LCT 的结构也不同）。
现在我们要 Access(N)，把 $A$ 到 $N$ 路径上的边都变为实边，拉成一棵 Splay。
实现的方法是从下到上逐步更新 Splay。
首先我们要把 $N$ 旋至当前 Splay 的根。
为了保证 AuxTree（辅助树）的性质，原来 $N$ 到 $O$ 的实边要更改为虚边。
由于认父不认子的性质，我们可以单方面的把 $N$ 的儿子改为 NULL。
于是原来的 AuxTree 就从下图变成了下下图。
下一步，我们把 $N$ 指向的 Father $I$ 也旋转到 $I$ 的 Splay 树根。
原来的实边 $I$ — $K$ 要去掉，这时候我们把 $I$ 的右儿子指向 $N$ ，就得到了 $I$ — $L$ 这样一棵 Splay。
接下来，按照刚刚的操作步骤，由于 $I$ 的 Father 指向 $H$ ，我们把 $H$ 旋转到他所在 Splay Tree 的根，然后把 $H$ 的 rs 设为 $I$ 。
之后的树是这样的。
同理我们 Splay(A)，并把 $A$ 的右儿子指向 $H$ 。
于是我们得到了这样一棵 AuxTree。并且发现 $A$ — $N$ 的整个路径已经在同一棵 Splay 中了。

// 回顾一下代码
int Access(int x) {
  int p;
  for (p = 0; x; p = x, x = f[x]) {
    Splay(x), ch[x][1] = p, PushUp(x);
  }
  return p;
}

我们发现 Access() 其实很容易，只有如下四步操作：

把当前节点转到根。
把儿子换成之前的节点。
更新当前点的信息。
把当前点换成当前点的父亲，继续操作。

这里提供的 Access 还有一个返回值。这个返回值相当于最后一次虚实链变换时虚边父亲节点的编号。该值有两个含义：

连续两次 Access 操作时，第二次 Access 操作的返回值等于这两个节点的 LCA.
表示 $x$ 到根的链所在的 Splay 树的根。这个节点一定已经被旋转到了根节点，且父亲一定为空。

`Update()`

// 从上到下一层一层 pushDown 即可
void Update(int p) {
  if (!isRoot(p)) Update(f[p]);
  pushDown(p);
}

`makeRoot()`

Make_Root() 的重要性丝毫不亚于 Access()。我们在需要维护路径信息的时候，一定会出现路径深度无法严格递增的情况，根据 AuxTree 的性质，这种路径是不能出现在一棵 Splay 中的。
这时候我们需要用到 Make_Root()。
Make_Root() 的作用是使指定的点成为原树的根，考虑如何实现这种操作。
设 Access(x) 的返回值为 $y$ ，则此时 $x$ 到当前根的路径恰好构成一个 Splay，且该 Splay 的根为 $y$ .
考虑将树用有向图表示出来，给每条边定一个方向，表示从儿子到父亲的方向。容易发现换根相当于将 $x$ 到根的路径的所有边反向（请仔细思考）。
因此将 $x$ 到当前根的路径翻转即可。
由于 $y$ 是 $x$ 到当前根的路径所代表的 Splay 的根，因此将以 $y$ 为根的 Splay 树进行区间翻转即可。

void makeRoot(int p) {
  p = Access(p);
  swap(ch[p][0], ch[p][1]);
  tag[p] ^= 1;
}

`Link()`

Link 两个点其实很简单，先 Make_Root(x)，然后把 $x$ 的父亲指向 $y$ 即可。显然，这个操作肯定不能发生在同一棵树内，所以记得先判一下。

void Link(int x, int p) {
  makeRoot(x);
  splay(x);
  f[x] = p;
}

`Split()`

Split 操作意义很简单，就是拿出一棵 Splay，维护的是 $x$ 到 $y$ 的路径。
先 MakeRoot(x)，然后 Access(y)。如果要 $y$ 做根，再 Splay(y)。
另外 Split 这三个操作可以直接把需要的路径拿出到 $y$ 的子树上，可以进行其他操作。

`Cut()`

Cut 有两种情况，保证合法和不一定保证合法。
如果保证合法，直接 Split(x, y)，这时候 $y$ 是根， $x$ 一定是它的儿子，双向断开即可。就像这样：

void Cut(int x, int p) { makeRoot(x), Access(p), Splay(p), ls = f[x] = 0; }

如果是不保证合法，我们需要判断一下是否有，这里选择使用 map 存一下，但是这里有一个利用性质的方法：

想要删边，必须要满足如下三个条件：

$x, y$ 连通。
$x, y$ 的路径上没有其他的链。
$x$ 没有右儿子。

总结一下，上面三句话的意思就一个： $x, y$ 之间有边。

具体实现就留作一个思考题给大家。判断连通需要用到后面的 Find，其他两点稍作思考分析一下结构就知道该怎么判断了。

`Find()`

Find() 查找的是 $x$ 所在的原树的根，请不要把原树根和辅助树根弄混。在 Access(p) 后，再 Splay(p)。这样根就是树里深度最小的那个，一直往左儿子走，沿途 PushDown 即可。
一直走到没有 ls，非常简单。
注意，每次查询之后需要把查询到的答案对应的结点 Splay 上去以保证复杂度。

int Find(int p) {
  Access(p);
  Splay(p);
  pushDown(p);
  while (ls) p = ls, pushDown(p);
  Splay(p);
  return p;
}

注意事项

操作前一定要想一想需不需要 PushUp 或者 PushDown，LCT 由于特别灵活的原因，少 Pushdown 或者 Pushup 一次就可能把修改改到不该改的点上！
LCT 的 Rotate 和 Splay 的不太一样，if (z) 一定要放在前面。
LCT 的 Splay 操作就是旋转到根，没有旋转到谁儿子的操作，因为不需要。

时间复杂度

LCT 中的大部分操作都基于 Access，其余操作的时间复杂度都为常数，因此我们只需要分析 Access 操作的时间复杂度。

其中，Access 的时间复杂度主要来自于多次 splay 操作和对路径中虚边的访问，接下来分别分析这两部分的时间复杂度。

splay
- 定义 $w (x) = \log s i z e (x)$ ，其中 $s i z e (x)$ 表示以 $x$ 为根的所有虚边和实边的数量之和。
- 定义势能函数 $Φ = \sum_{x \in T} w (x)$ ，其中 $T$ 表示所有节点的集合。

由 Splay 的时间复杂度分析易知，splay 操作的均摊时间复杂度为 $O (\log n)$ 。

访问虚边

参考重链剖分，定义两种虚边：
- 重虚边：从节点 $v$ 到其父节点的虚边，其中 $s i z e (v) > \frac{1}{2} s i z e (p a r e n t (v))$ 。
- 轻虚边：从节点 $v$ 到其父节点的虚边，其中 $s i z e (v) \leq \frac{1}{2} s i z e (p a r e n t (v))$ 。
对于虚边的处理，可以使用势能分析，定义势能函数 $Φ$ 为所有重虚边的数量，定义均摊成本 $c_{i} = t_{i} + Δ Φ_{i}$ ，其中 $t_{i}$ 为实际操作的成本， $Δ Φ_{i}$ 为势能的变化。
- 走过重虚边后，会将重虚边转换为实边，该操作会减少 $1$ 的势能，因为它通过加强重要连接来优化树的结构。且由于其实际操作成本为 $O (1)$ ，抵消了势能的增加，故不会增加均摊成本，所有的均摊成本集中在轻虚边的处理上。
- 每次 Access 操作最多遍历 $O (\log n)$ 条轻虚边，因此至多消耗 $O (\log n)$ 的实际操作成本，转化得到 $O (\log n)$ 条重虚边，即势能以 $O (\log n)$ 的代价增加。
由此，最终访问虚边的均摊复杂度为实际操作成本和势能变化的和，即 $O (\log n)$ 。

综上所述，LCT 中 Access 操作的时间复杂度是 splay 和虚边访问的复杂度之和，因此最后的均摊复杂度为 $O (\log n)$ ，即 n 个节点的 LCT，做 m 次 Access 操作的时间复杂度为 $O (n \log n + m \log n)$ ，从而基于 Access 操作的 Cut,Link,Findroot 等操作的均摊复杂度也为 $O (\log n)$ 。

习题

维护树链信息

LCT 通过 Split(x,y) 操作，可以将树上从点 $x$ 到点 $y$ 的路径提取到以 $y$ 为根的 Splay 内，树链信息的修改和统计转化为平衡树上的操作，这使得 LCT 在维护树链信息上具有优势。此外，借助 LCT 实现的在树链上二分比树链剖分少一个 $O (\log n)$ 的复杂度。

例题「国家集训队」Tree II

给出一棵有 $n$ 个结点的树，每个点的初始权值为 $1$ 。 $q$ 次操作，每次操作均为以下四种之一：

- u1 v1 u2 v2：将树上 $u_{1}, v_{1}$ 两点之间的边删除，连接 $u_{2}, v_{2}$ 两点，保证操作合法且连边后仍是一棵树。
+ u v c：将树上 $u, v$ 两点之间的路径上的点权都增加 $c$ 。
* u v c：将树上 $u, v$ 两点之间的路径上的点权都乘以 $c$ 。
/ u v：输出树上 $u, v$ 两点之间的路径上的点权之和对 $51061$ 取模后的值。

$1 \leq n, q \leq 10^{5}, 0 \leq c \leq 10^{4}$

- 操作可以直接 Cut(u1,v1),Link(u2,v2)。

对树上 $u, v$ 两点之间的路径进行修改时，先 Split(u,v)。

此题要求进行在辅助树上的子树加，子树乘，子树求和操作，所以我们除了一般 LCT 需要维护的子树翻转标记，还要维护子树加法标记和子树乘法标记。处理标记的方法和在 Splay 上是一样的。

在打上和下传加法标记时，子树权值和的变化量和子树中的结点数有关，所以我们还要维护子树的大小 siz。

在下传标记时，需要注意顺序，先下传乘法标记再下传加法标记。子树翻转和子树加乘两种标记没有冲突。

参考代码

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
constexpr long long MAXN = 100010;
constexpr long long mod = 51061;
long long n, q, u, v, c;
char op;

struct Splay {
  long long ch[MAXN][2], fa[MAXN], siz[MAXN], val[MAXN], sum[MAXN], rev[MAXN],
      add[MAXN], mul[MAXN];

  void clear(long long x) {
    ch[x][0] = ch[x][1] = fa[x] = siz[x] = val[x] = sum[x] = rev[x] = add[x] =
        0;
    mul[x] = 1;
  }

  long long getch(long long x) { return (ch[fa[x]][1] == x); }

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

  void maintain(long long x) {
    clear(0);
    siz[x] = (siz[ch[x][0]] + 1 + siz[ch[x][1]]) % mod;
    sum[x] = (sum[ch[x][0]] + val[x] + sum[ch[x][1]]) % mod;
  }

  void pushdown(long long x) {
    clear(0);
    if (mul[x] != 1) {
      if (ch[x][0])
        mul[ch[x][0]] = (mul[x] * mul[ch[x][0]]) % mod,
        val[ch[x][0]] = (val[ch[x][0]] * mul[x]) % mod,
        sum[ch[x][0]] = (sum[ch[x][0]] * mul[x]) % mod,
        add[ch[x][0]] = (add[ch[x][0]] * mul[x]) % mod;
      if (ch[x][1])
        mul[ch[x][1]] = (mul[x] * mul[ch[x][1]]) % mod,
        val[ch[x][1]] = (val[ch[x][1]] * mul[x]) % mod,
        sum[ch[x][1]] = (sum[ch[x][1]] * mul[x]) % mod,
        add[ch[x][1]] = (add[ch[x][1]] * mul[x]) % mod;
      mul[x] = 1;
    }
    if (add[x]) {
      if (ch[x][0])
        add[ch[x][0]] = (add[ch[x][0]] + add[x]) % mod,
        val[ch[x][0]] = (val[ch[x][0]] + add[x]) % mod,
        sum[ch[x][0]] = (sum[ch[x][0]] + add[x] * siz[ch[x][0]] % mod) % mod;
      if (ch[x][1])
        add[ch[x][1]] = (add[ch[x][1]] + add[x]) % mod,
        val[ch[x][1]] = (val[ch[x][1]] + add[x]) % mod,
        sum[ch[x][1]] = (sum[ch[x][1]] + add[x] * siz[ch[x][1]] % mod) % mod;
      add[x] = 0;
    }
    if (rev[x]) {
      if (ch[x][0]) rev[ch[x][0]] ^= 1, swap(ch[ch[x][0]][0], ch[ch[x][0]][1]);
      if (ch[x][1]) rev[ch[x][1]] ^= 1, swap(ch[ch[x][1]][0], ch[ch[x][1]][1]);
      rev[x] = 0;
    }
  }

  void update(long long x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void print(long long x) {
    if (!x) return;
    pushdown(x);
    print(ch[x][0]);
    printf("%lld ", x);
    print(ch[x][1]);
  }

  void rotate(long long x) {
    long long y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
    maintain(y);
    maintain(x);
    maintain(z);
  }

  void splay(long long x) {
    update(x);
    for (long long f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

  void access(long long x) {
    for (long long f = 0; x; f = x, x = fa[x])
      splay(x), ch[x][1] = f, maintain(x);
  }

  void makeroot(long long x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    rev[x] ^= 1;
  }

  long long find(long long x) {
    access(x);
    splay(x);
    while (ch[x][0]) x = ch[x][0];
    splay(x);
    return x;
  }
} st;

main() {
  scanf("%lld%lld", &n, &q);
  for (long long i = 1; i <= n; i++) st.val[i] = 1, st.maintain(i);
  for (long long i = 1; i < n; i++) {
    scanf("%lld%lld", &u, &v);
    if (st.find(u) != st.find(v)) st.makeroot(u), st.fa[u] = v;
  }
  while (q--) {
    scanf(" %c%lld%lld", &op, &u, &v);
    if (op == '+') {
      scanf("%lld", &c);
      st.makeroot(u), st.access(v), st.splay(v);
      st.val[v] = (st.val[v] + c) % mod;
      st.sum[v] = (st.sum[v] + st.siz[v] * c % mod) % mod;
      st.add[v] = (st.add[v] + c) % mod;
    }
    if (op == '-') {
      st.makeroot(u);
      st.access(v);
      st.splay(v);
      if (st.ch[v][0] == u && !st.ch[u][1]) st.ch[v][0] = st.fa[u] = 0;
      scanf("%lld%lld", &u, &v);
      if (st.find(u) != st.find(v)) st.makeroot(u), st.fa[u] = v;
    }
    if (op == '*') {
      scanf("%lld", &c);
      st.makeroot(u), st.access(v), st.splay(v);
      st.val[v] = st.val[v] * c % mod;
      st.sum[v] = st.sum[v] * c % mod;
      st.mul[v] = st.mul[v] * c % mod;
    }
    if (op == '/')
      st.makeroot(u), st.access(v), st.splay(v), printf("%lld\n", st.sum[v]);
  }
  return 0;
}

习题

维护连通性质

判断是否连通

借助 LCT 的 Find() 函数，可以判断动态森林上的两点是否连通。如果有 Find(x)==Find(y)，则说明 $x, y$ 两点在一棵树上，相互连通。

例题「SDOI2008」洞穴勘测

一开始有 $n$ 个独立的点， $m$ 次操作。每次操作为以下之一：

Connect u v：在 $u, v$ 两点之间连接一条边。
Destroy u v：删除在 $u, v$ 两点之间的边，保证之前存在这样的一条边。
Query u v：询问 $u, v$ 两点是否连通。

保证在任何时刻图的形态都是一个森林。

$n \leq 10^{4}, m \leq 2 \times 10^{5}$

参考代码

#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
constexpr int MAXN = 10010;

struct Splay {
  int ch[MAXN][2], fa[MAXN], tag[MAXN];

  void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = tag[x] = 0; }

  int getch(int x) { return ch[fa[x]][1] == x; }

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

  void pushdown(int x) {
    if (tag[x]) {
      if (ch[x][0]) swap(ch[ch[x][0]][0], ch[ch[x][0]][1]), tag[ch[x][0]] ^= 1;
      if (ch[x][1]) swap(ch[ch[x][1]][0], ch[ch[x][1]][1]), tag[ch[x][1]] ^= 1;
      tag[x] = 0;
    }
  }

  void update(int x) {
    if (!isroot(x)) update(fa[x]);
    pushdown(x);
  }

  void rotate(int x) {
    int y = fa[x], z = fa[y], chx = getch(x), chy = getch(y);
    fa[x] = z;
    if (!isroot(y)) ch[z][chy] = x;
    ch[y][chx] = ch[x][chx ^ 1];
    fa[ch[x][chx ^ 1]] = y;
    ch[x][chx ^ 1] = y;
    fa[y] = x;
  }

  void splay(int x) {
    update(x);
    for (int f = fa[x]; f = fa[x], !isroot(x); rotate(x))
      if (!isroot(f)) rotate(getch(x) == getch(f) ? f : x);
  }

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

  void makeroot(int x) {
    access(x);
    splay(x);
    swap(ch[x][0], ch[x][1]);
    tag[x] ^= 1;
  }

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

int n, q, x, y;
char op[MAXN];

int main() {
  scanf("%d%d", &n, &q);
  while (q--) {
    scanf("%s%d%d", op, &x, &y);
    if (op[0] == 'Q') {
      if (st.find(x) == st.find(y))
        printf("Yes\n");
      else
        printf("No\n");
    }
    if (op[0] == 'C')
      if (st.find(x) != st.find(y)) st.makeroot(x), st.fa[x] = y;
    if (op[0] == 'D') {
      st.makeroot(x);
      st.access(y);
      st.splay(y);
      if (st.ch[y][0] == x && !st.ch[x][1]) st.ch[y][0] = st.fa[x] = 0;
    }
  }
  return 0;
}

维护边双连通分量

如果要求将边双连通分量缩成点，每次添加一条边，所连接的树上的两点如果相互连通，那么这条路径上的所有点都会被缩成一个点。

例题「AHOI2005」航线规划

给出 $n$ 个点，初始时有 $m$ 条无向边， $q$ 次操作，每次操作为以下之一：

0 u v：删除 $u, v$ 之间的连边，保证此时存在这样的一条边。
1 u v：查询此时 $u, v$ 两点之间可能的所有路径必须经过的边的数量。

保证图在任意时刻都连通。

$1

本页面最近更新：2024/12/4 12:44:49，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：hsfzLZH1, Ir1d, sshwy, Tiphereth-A, Early0v0, Marcythm, ChungZH, i-yyi, mao1t, ouuan, Xeonacid, abc1763613206, Chrogeek, Henry-ZHR, StudyingFather, 9lie, alphagocc, Backl1ght, CCXXXI, CoderOJ, diauweb, Enter-tainer, GavinZhengOI, HeRaNO, ksyx, lirunzhe, Macesuted, mcendu, Molmin, Mout-sea, r-value, Sheng-Horizon, shuzhouliu, thredreams, vincent-163, yuhuoji, yyyu-star
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用