题目描述

动态树模板题两道。

[lydsy2049]洞穴勘测：维护一棵树，支持如下操作：

  1. Connect u v 连接两点 u, v (保证 u, v 不连通)。
  2. Destroy u v 删除两点 u, v 之间的边(保证 u, v 连通)。
  3. Query u v 询问 u, v 的连通性。

[luogu3690]【模板】Link Cut Tree：维护一棵树，每个点有一个对应的权值 wi，支持如下操作：

  1. 询问 x, y 路径上的点权异或和。
  2. 连接两点 x, y (如果 x, y 连通，则忽略本操作)。
  3. 删除两点 x, y 之间的边 (如果 x, y 不连通，则忽略本操作)。
  4. wx ← y。

输入输出格式

没什么好说的，见原题。

[lydsy2049]洞穴勘测

[luogu3690]【模板】Link Cut Tree

题解

终于学动态树了！

你知道什么是动态树吗？左图就是一棵动态树。

动态树是维护一棵可以动态加边删边的树，然后在树上搞神马树剖啦，LCA啦，仙人掌嵌套动态网络流维护A*搜索等等。

哦对了，有人问我第一题能不能用并查集骗，其实第一题去掉 Destroy 操作可以用并查集做，说的也没错，可是并查集貌(di)似(que)是不支持动态加删边的。(不过好像这道题用并查集能拿很高的分)

动态树其实有很多种，最(wo)主(zhi)流(hui)的动态树就是 Link-Cut Tree，简称 LCT。

LCT 就是将一棵树先进行树链剖分(没有学过树剖的自行左转小学(没错，就是小学)深造)。

将这棵树剖成几条重重轻轻的链以后，然后用 spaly，哦不，splay 维护每个链的形态。

(scx: 不应该是线段树么？splay 是平衡树，是维护一棵有序序列的！)

线段树是可以用，但是 splay 会有更高的效率，splay 是维护这样一个东西：

假如有一棵重链(显然是单调上升或单调下降的)，因此可以唯一地将这个链上的点从浅至深的遍历

那么，我们只需使这个 splay 的每一个节点的左子树存储比它浅的节点，右子树存储比它深的节点，那么将它中序遍历一下，就是刚才所说的从浅至深的遍历。

(scx: 那么我们怎么知道要多少个splay呢？如何保证内存呢？)

其实不难。我们可以见一个主splay，如果一条重链的最顶端不是根，设这个点 V 的父亲为 U，我们知道，这时点 V 在这个 splay 的最左端，而它所在子树的根节点没有父亲，所以我们将那个根节点的父亲设为 U，但它不作为节点 U 的任何子树，我们将这样的边叫做虚边(void edge)。

这样，所有的 splay 并成了一棵树，把它叫做辅助树(auxiliary tree)，这棵树所表示的，也就是题目中的原来的树，叫做原树(primary tree)，这样，我们把原树的几乎所有信息转移到了辅助树上。

(scx: 那如何在这棵辅助树上动态加(删)边呢？)

我们需要这样几个操作：

  1. Dir操作：像平常的 splay 一样，得到该树的方向(即是父亲的左子树还是右子树，左返回 0，右返回 1)，但是因为虚边的存在，我们还需要判断如果既不是左子树又不是右子树，则说明它是它所属 splay 的根，给出一个新的返回值(我习惯用 -1)。
  2. Rotate操作：这个和普通的 splay 毫无区别(我假装来阅读此文的人已经会熟练运用 splay)。
  3. Pull_down操作：(scx: 我只听说过 push_down，这个 pull_down 又是什么鬼？)
    pull_down 其实就是把该点所在 splay 的根节点一直 push_down 到该节点，实现非常简单： 
    void pull_down(int x){
    if(~dir(x)) pull_down(x[nd].p);
    push_down(x);
}
  4. Push_down操作：这个其实是用来下传翻转标记的...和线段树差不多吧...
  5. Reverse操作：让该节点以下的部分左右翻转，由于翻转的节点过多，所以要像线段树一样先交换这个节点的左右儿子，再下传标记(push_down)。
  6. Splay操作：和 splay 的 splay 操作没什么区别，唯一的不同就是一开始需要 pull_down (不让你怎么知道这棵树有没有被别人翻来翻去？)
  7. Access操作(和根联系)：将原树中该点与子节点的重链切断(如果有)，然后将原树中该点到根重新产生一条重链。所以我们只需将原来这个点翻到顶，将 splay 中右儿子(即原树中的儿子)设为上一次操作的点(第一次为 0)。然后令当前的点为它的父亲，重复此操作，操作完毕后，这个点和原树的根节点在同一棵 splay 中。
  8. Make_root操作(让树翻转起来吧)：将一个点设为原树的根。记住，要将一个点在原树中搞什么操作，先把这个点 access 了，即和根有联系了，然后将它 splay 到顶，于是成了该 splay (就是整个辅助树)的根，因为 splay 平衡树维护的是深度，然而 access 后它和子节点不在同一个 splay 上，所以只需要将 splay 左右翻转(reverse操作)，然后中序遍历的结果就是原结果的反序，该节点已经是最左边的节点了，其实就已经成为原树的根了。
  9. Link操作(牵手吧)：其实很简单，将其中一个点设为根后，再与另外一个节点连一条虚边(即让根节点的父亲设为第二个点)就可以了，这个 Link 操作是保证原先两点不连通，不然可能会发生错误。
  10. Cut操作(分手吧)： 其实也不难，先将其中一个点设为根，另外一个点与根联系，在设为辅助树的根。如果两点有直接连边的话，那么当第一个点设为根的时候，第二个点的深度为 1，所以当它成为 splay 的根的时候，由于 access 之后，它与原树的根(第一个点)在同一棵 splay 上，所以它的左子树有且仅有一个节点，即第一个点，把这条边断了即可。
  11. Find_root操作(找找祖先)：(scx: 那么如何知道两点的连通性？)
    这个和并查集有点像，两点联通当且仅当这个两个点所在原树的根为同一个。所以我们需要写一个算法求出该点所在原树的根。
    操作的话，先将它与根联系再 splay 到根，那么(原树的)根应该是它所属 splay 的深度最小节点(最左边)，所以我们只需寻找这棵 splay 的最小节点，即有左子树就向左寻找，直到没有左子树，就是最小节点。

这样就能实现一个基本的 splay 了，代码见"代码"部分，如果还有维护神马东西的话，增加一个 Update 函数，更新维护的权值，只需在 rotate、access、cut 时增加一句 update 即可。

两道题还有一个区别，就是第一题的 link, cut 有连通性保证，第二题没有，所以代码也会有区别(本例中改为了 Trylink, Trycut 函数)。

毕竟这两道题是动态树模板题，所以其它也没什么好讲的了。

代码

lydsy2049(略压代码)

#include <bits/stdc++.h>
#define LEFT 0
#define RIGHT 1
#define pa p[nd]
#define root nd[0].c[0]
#define N 10034
using namespace std;

struct node{
    int v, rev;
    int c[2], p;
}nd[N];

// get direction of x, root: -1, left: 0, right: 1
inline int dir(int x){return !x[nd].p ? -1 : (x == x[nd].pa.c[LEFT] ? 0 : (x == x[nd].pa.c[RIGHT] ? 1 : -1));}

// reverse the subtree of x
void reverse(int x){swap(x[nd].c[LEFT], x[nd].c[RIGHT]); x[nd].rev ^= 1;}

// push_down the tags
void push_down(int x){if(x[nd].rev){reverse(x[nd].c[LEFT]); reverse(x[nd].c[RIGHT]);} x[nd].rev = 0;}

// push_down all the tags over x 
void pull_down(int x){if(~dir(x)) pull_down(x[nd].p); push_down(x);}

// rotate node x
void rotate(int x){
    int y = x[nd].p, d = !dir(x);
    nd[y[nd].c[!d] = x[nd].c[d]].p = y; // change the subtree
    x[nd].p = y[nd].p; // change the parent of parent
    if(~dir(y)) y[nd].pa.c[dir(y)] = x;
    nd[x[nd].c[d] = y].p = x; // change itself and parent
}

// splay x to root
void splay(int x){for(pull_down(x); ~dir(x); rotate(x))
    if(~dir(x[nd].p)) rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p);}

// turn all the edge from x into root into preferred edge
void access(int x){for(int y = 0; x; y = x, x = x[nd].p){splay(x); x[nd].c[RIGHT] = y;}}

// make x to root
void make_root(int x){access(x); splay(x); reverse(x);}

// link edge {x, y}
void link(int x, int y){make_root(x); x[nd].p = y;}

// cut edge {x, y}
void cut(int x, int y){make_root(x); access(y); splay(y); y[nd].c[LEFT] = x[nd].p = 0;}

// find the root of temp tree of x
int find_root(int x){access(x); splay(x); for(; x[nd].c[LEFT]; x = x[nd].c[LEFT]); return x;}

int V, Q;
int u, v, ur, vr;
char op[16];

int main(){
    scanf("%d%d", &V, &Q);
    for(; Q; Q--){
        scanf("%s%d%d", op, &u, &v);
        if(op[0] == 'C') link(u, v);
        else if(op[0] == 'D') cut(u, v);
        else if(op[0] == 'Q'){
            ur = find_root(u); vr = find_root(v);
            puts(ur == vr ? "Yes" : "No");
        }
    }
}

luogu3690

#include <bits/stdc++.h>
#define LEFT 0
#define RIGHT 1
#define pa p[nd]
#define root nd[0].c[0]
#define N 300034
using namespace std;

struct node{
    int v, rev;
    int c[2], p;
}nd[N];

int a[N];

int dir(int x){
    return !x[nd].p ? -1 : (x == x[nd].pa.c[LEFT] ? 0 : (x == x[nd].pa.c[RIGHT] ? 1 : -1));
}

void reverse(int x){
    swap(x[nd].c[LEFT], x[nd].c[RIGHT]);
    x[nd].rev ^= 1;
}

void push_down(int x){
    if(x[nd].rev){reverse(x[nd].c[LEFT]); reverse(x[nd].c[RIGHT]);}
    x[nd].rev = 0;
}

void pull_down(int x){
    if(~dir(x)) pull_down(x[nd].p);
    push_down(x);
}

void update(int x){
    x[nd].v = x[nd].c[LEFT][nd].v ^ x[nd].c[RIGHT][nd].v ^ a[x];
}

void rotate(int x){
    int y = x[nd].p, d = !dir(x);
    nd[y[nd].c[!d] = x[nd].c[d]].p = y;
    x[nd].p = y[nd].p;
    if(~dir(y)) y[nd].pa.c[dir(y)] = x;
    nd[x[nd].c[d] = y].p = x;
    update(y); update(x);
}

void splay(int x){
    for(pull_down(x); ~dir(x); rotate(x))
        if(~dir(x[nd].p))
            rotate(dir(x) ^ dir(x[nd].p) ? x : x[nd].p);
}

void access(int x){
    for(int y = 0; x; y = x, x = x[nd].p){
        splay(x);
        x[nd].c[RIGHT] = y;
        update(x);
    }
}

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

int find_root(int x){
    access(x); splay(x); for(; x[nd].c[LEFT]; x = x[nd].c[LEFT]); return x;
}

void trylink(int x, int y){
    make_root(x);
    if(find_root(y) != x) x[nd].p = y;
}

void split(int x, int y){
    make_root(x); access(y); splay(y);
}

void trycut(int x, int y){
    split(x, y);
    if(y[nd].c[LEFT] == x) x[nd].p = y[nd].c[LEFT] = 0; update(y);
}

int V, Q, i;
int ch, u, v;

int main(){
    scanf("%d%d", &V, &Q);
    for(i = 1; i <= V; i++)
        scanf("%d", a + i);
    for(; Q; Q--){
        scanf("%d%d%d", &ch, &u, &v);
        switch(ch){
            case 0:
                split(u, v);
                printf("%d\n", nd[v].v);
                break;
            case 1:
                trylink(u, v);
                break;
            case 2:
                trycut(u, v);
                break;
            case 3:
                access(u);
                splay(u);
                a[u] = v;
                update(u);
                break;
        }
    }
    return 0;
}

坑

毕竟是个 LCT 的裸题，抄着模板写起来还是比较顺畅的。抄好后为了保证熟练，以后定下目标，每天编程前码一遍 LCT。

(scx: 这看起来很累啊，你能做到吗？)

大概就是码两个月后，如果平均能在 5 min 中内码完且没有错误，那么就可以适当降低频率。

当时我做 lydsy 的题时，是照着板子抄的，那道洛谷题时，我试着自己码了一遍，7 分钟码完了，还过了样例，然后交上去总是 WA ...

(scx: 感觉你好几次都是过了样例提交就 WA ...)

我也觉得奇怪，然后开始调我手码的 LCT (你要知道 LCT 码萎了不是那么好调的)，然后先照着 AC 的那次代码对了 4 遍，可能是我眼力比较差，没查出来，然后开始疯狂调试 ... 调了 2 个多小时，才发现是一个旋转写炸了 ...

当时把

nd[y[nd].c[!d] = x[nd].c[d]].p = y;
写成了
nd[y[nd].c[!d] = x[nd].c[d]].p = x;

结果浪费了 2 个小时……(代码技术差要人命啊)