关键词：
从这里开始
动态树问题和Link Cut Tree
动态树问题是一类要求维护一个有根树森林，支持对树的分割, 合并等操作的问题。
Link Cut Tree（林可砍树？简称LCT）是解决这一类问题的一种数据结构。
一些无聊的定义
Link Cut Tree维护的是动态森林中每棵树的任意链剖分。
Preferred Child，每个点偏好的子节点，对于每个点，要么它没有，要么它只有一个。
Preferred Edge，连接每个点和它偏好的子节点的边，以下简称为实边。
相对地，对于非实边的边，以下简称为虚边。
Preferred Path，由Preferred Edge 连接成的不可再延伸的路径。以下简称为实链。特殊地，如果与一个点相连的所有边都是虚边，那么这一个点独自构成一条实链。
显然，所有实链覆盖所有的点。
对于每条实链，LCT用一颗Splay对节点按深度为关键字进行维护。
//接下来会默认读者能熟练地敲打Splay的板子
为了方便直接用Splay森林来维护。对于每棵Splay，它还需要维护它的维护的实链的顶端（深度最小的点）的父节点，这个记在根结点上。
access操作
access操作是将某个节点$x$到根的路径变为实链。
由图中可以看出，access操作可以看成以下几个操作的反复进行：
- 断掉当前实链中当前点和比它深的点之间的实边
- 合并当前实链和上一条实链
- 访问实链顶端的父节点
当当前点为空的时候结束，不存在上一条实链的时候它为空。
显然这样操作恰好将指定点到根的路径变为实链了。
1 void access(SplayNode *p) { 2 SplayNode* q = NULL; 3 while (p) { 4 splay(p); 5 q = p, p = p->fa; 6 } 7 }
换根操作
将一棵树的根变为指定点。
考虑换根操作的影响：
只是旧根到新根的路径被翻转了。那就先对新根执行access操作，然后打反转标记就好了。
1 void mkroot(SplayNode* node) { 2 access(node); 3 splay(node); 4 node->rev ^= 1; 5 }
link和cut操作
link操作是连接两个不连通的点，cut操作是删除一条原有的边。
考虑link操作，将其中一个作为根然后向另一个点连接一条虚边即可。
考虑cut操作，将其中一个作为根，然后对另一个点做access操作，这样恰好根所在的Splay中的后继是另一个点，Splay树上断掉这条边即可。
1 void link(int u, int v) { 2 SplayNode* p = pool + u, *q = pool + v; 3 if(isConnected(p, q)) return ; 4 mkroot(q); 5 q->fa = p, splay(q); 6 } 7 8 void cut(int u, int v) { 9 SplayNode* p = pool + u, *q = pool + v; 10 mkroot(p); 11 access(q); 12 splay(q); 13 q->ch[0] = p->fa = NULL; 14 }
例1 Cave 洞穴勘测
题目大意
给定一个动态森林，要求支持加边、删边和询问两点之间的连通性。
判断两点之间是否连通，等价于它们所在的树的根相同。
所以考虑如何找一个点所在树的根。
首先access这个点，然后把它伸展到根，然后暴力跳左子树就好了。
Code
1 /** 2 * bzoj 3 * Problem#2049 4 * Accepted 5 * Time: 1976ms 6 * Memory: 1500k 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 typedef bool boolean; 11 12 typedef class SplayNode { 13 public: 14 boolean rev; 15 SplayNode *ch[2]; 16 SplayNode *fa; 17 18 SplayNode():rev(0), ch({NULL, NULL}), fa(NULL) { } 19 20 boolean isRoot() { 21 if(fa == NULL) return true; 22 return fa->ch[0] != this && fa->ch[1] != this; 23 } 24 25 void pushDown() { 26 swap(ch[0], ch[1]); 27 if(ch[0]) ch[0]->rev ^= 1; 28 if(ch[1]) ch[1]->rev ^= 1; 29 rev = 0; 30 } 31 }SplayNode; 32 33 typedef class LinkCutTree { 34 public: 35 SplayNode *pool; 36 37 LinkCutTree():pool(NULL) { } 38 LinkCutTree(int n) { 39 pool = new SplayNode[(n + 1)]; 40 } 41 42 void rotate(SplayNode* node) { 43 SplayNode* fa = node->fa; 44 boolean aFlag = fa->isRoot(); 45 int d = fa->ch[1] == node; 46 fa->ch[d] = node->ch[d ^ 1]; 47 node->fa = fa->fa; 48 fa->fa = node; 49 node->ch[d ^ 1] = fa; 50 if(fa->ch[d]) fa->ch[d]->fa = fa; 51 if(!aFlag) node->fa->ch[node->fa->ch[1] == fa] = node; 52 } 53 54 SplayNode* s[10005]; 55 void splay(SplayNode* node) { 56 int top = 0; 57 s[++ top] = node; 58 for (SplayNode* p = node; !p -> isRoot(); p = p->fa) s[++ top] = p -> fa; 59 for (int i = top; i; -- i) if (s[i] -> rev) s[i] -> pushDown(); 60 while(!node->isRoot()) { 61 SplayNode *fa = node->fa, *ffa = fa->fa; 62 if(fa->isRoot()) { 63 rotate(node); 64 break; 65 } 66 int d1 = (fa->ch[1] == node), d2 = ffa->ch[1] == fa; 67 if(d1 == d2) 68 rotate(fa); 69 else 70 rotate(node); 71 rotate(node); 72 } 73 } 74 75 SplayNode* findSplayRoot(SplayNode* node) { 76 access(node); 77 // while(node->fa) node = node->fa; 78 splay(node); 79 while(node->ch[0]) node = node->ch[0]; 80 return node; 81 } 82 83 void access(SplayNode* node) { 84 SplayNode* p = NULL; 85 do { 86 splay(node); 87 node->ch[1] = p; 88 p = node; 89 node = node->fa; 90 } while (node); 91 } 92 93 boolean isConnected(SplayNode* p, SplayNode* q) { 94 return findSplayRoot(p) == findSplayRoot(q); 95 } 96 97 void mkroot(SplayNode* node) { 98 access(node); 99 splay(node); 100 node->rev ^= 1; 101 } 102 103 void link(int u, int v) { 104 SplayNode* p = pool + u, *q = pool + v; 105 if(isConnected(p, q)) return ; 106 mkroot(q); 107 q->fa = p, splay(q); 108 } 109 110 void cut(int u, int v) { 111 SplayNode* p = pool + u, *q = pool + v; 112 mkroot(p); 113 access(q); 114 splay(q); 115 q->ch[0] = p->fa = NULL; 116 } 117 118 boolean isConnected(int u, int v) { 119 return isConnected(pool + u, pool + v); 120 } 121 }LinkCutTree; 122 123 int n, m; 124 LinkCutTree lct; 125 char buf[15]; 126 int u, v; 127 inline void solve() { 128 scanf("%d%d", &n, &m); 129 lct = LinkCutTree(n); 130 while(m--) { 131 scanf("%s%d%d", buf, &u, &v); 132 switch(buf[0]) { 133 case 'C': 134 lct.link(u, v); 135 break; 136 case 'D': 137 lct.cut(u, v); 138 break; 139 case 'Q': 140 puts((lct.isConnected(u, v)) ? ("Yes") : ("No")); 141 break; 142 } 143 } 144 } 145 146 int main() { 147 solve(); 148 return 0; 149 }
时间复杂度证明
如果学习一个数据结构能证明它的时间复杂度那就再好不过了。
对于LCT的操作，基本上是access，然后加上某些$O(1)$的操作或者均摊$O(\log n)$的Splay操作。所以只需要证明access的时间复杂度是$O(\log n)$即可。
在开始证明前，你需要知道Splay的时间复杂度和一些常识性的东西。
定理1 对于操作splay(x)，设操作前$x$的子树大小为$siz[x]$，操作后的子树大小为$siz'[x]$，splay(x)的均摊时间复杂度小于等于$3(\log siz'[x] - \log siz[x]) + 1$
证明略去（其实是我不会）
下面一个是关于轻重链剖分的常识，证明可以看这篇随笔。
定理2 一条根节点到叶节点的路径上，轻边的条数不超过$\log_{2}n$条
然后还有一个需要证明的事情。
定理3 Preferred Child的改变次数均摊为$O(log_{2}n)$次
证明 因为每次Preferred Child的改变时会导致实边发生改变。所以考察实边改变的次数即可。
这一部分可以分为两种情况：
- 一条轻虚边被改为轻实边。
- 一条重虚边被改为重实边。
因为轻边总数不超过$\log_{2}n$条，所以第一部分的改变次数不超过$\log_{2}n$次。
考虑重虚边被改为重实边的情况。
考虑每一条重边，它从实变为虚，虚变为实的过程是交替进行的。所以它被改为实边的次数不会超过它从实边被改为虚边的次数加1。
当一条重实边被改为重虚边会导致一条轻虚边变为轻实边，同时我们证明了轻虚边变为轻实边的均摊次数不超过$O(log_{2}n)$，所以一条重虚边被改为重实边的次数也不超过$O(log_{2}n)$。
因此定理得证。
定理4 access的均摊时间复杂度为$O(log_{2}n)$
证明 设每次设为当前点的点依次为$v_{0}, v_{1}, v_{2},\cdots,v_{k}$。
那么有：
$\widehat{cost}\leqslant 3\left (\sum_{i = 1}^{k}\log siz[v_{i}] - \log siz[v_{i - 1}] + 1 \right ) + \log siz[v_{0}]$
所以化简后再根据定理3，可得：
$\widehat{cost}\leqslant 6\log{n}$
Link Cut Tree维护链上信息
对于有关边权的链上信息考虑为每条边建一个虚点。然后和它两端连边。
查询链上信息可以通过把一个点变为根，access另一个点后的splay中的信息就是这条链上的信息。
但是有些装逼爱好者觉得这样不能满足他们的欲望，想出了一种不用建虚点的方法。很开心的是细节超多，看到neither_nor的某道题写了200+行，想想得到结论——装逼是要有代价的。
这个方法的讲解：neither_nor神犇的博客
例2 魔法森林
题目大意
一张图有$n$个点，$m$条边，第$i$条边有两个边权$a_{i}$和$b_{i}$。定义从1号点走到$n$号点的代价是经过边的所有$a$边权的最大值加上所有$b$边权的最大值。
问从1号点走到$n$号点的最小代价。
高维问题常见思路是降维，因此考虑按照$a$边权排序，然后枚举。
假设图开始是空的，然后依次加入每一条边。
- 如果边的两端未连通，直接加就好了。
- 如果边的两端连通，那么会形成环。根据人生的经验和图论的哲理，可以知道，环是这两点在树上的简单路径再加上这一条边。那么找到换上$b$边权最大的一条边比较它和当前边的$b$边权。如果当前边的$b$边权更小，那么就把树上的那条边cut掉，然后把这条新边加上。
如果在某个时候1和$n$连通，就查询一下它们之间的简单路径中$a$边权和$b$边权的最大值就好了。
由于这里的“删边”不会改变连通性（因为马上你会加一条边），所以可以直接用并查集维护连通性。
Code
1 /** 2 * uoj 3 * Problem#3 4 * Accepted 5 * Time: 2287ms 6 * Memory: 11208k 7 */ 8 #include <bits/stdc++.h> 9 using namespace std; 10 typedef bool boolean; 11 12 typedef class SplayNode { 13 public: 14 boolean rev; 15 int ea, eb, idx; 16 int ma, mb, ib; 17 SplayNode *ch[2]; 18 SplayNode *fa; 19 20 SplayNode():rev(false), ea(0), eb(0), idx(0), ma(0), mb(0), ib(0), ch({NULL, NULL}), fa(NULL) { } 21 22 void pushUp() { 23 ma = ea, mb = eb, ib = idx; 24 for (int i = 0; i < 2; i++) 25 if (ch[i]) { 26 (ch[i]->ma > ma) ? (ma = ch[i]->ma) : (0); 27 (ch[i]->mb > mb) ? (mb = ch[i]->mb, ib = ch[i]->ib) : (0); 28 } 29 } 30 31 void pushDown() { 32 swap(ch[0], ch[1]); 33 if (ch[0]) ch[0]->rev ^= 1; 34 if (ch[1]) ch[1]->rev ^= 1; 35 rev = false; 36 } 37 38 boolean isroot() { 39 return !fa || (fa->ch[0] != this && fa->ch[1] != this); 40 } 41 42 int which() { 43 return (!isroot()) ? (fa->ch[1] == this) : (-1); 44 } 45 }SplayNode; 46 47 typedef class LinkCutTree { 48 public: 49 SplayNode* pool; 50 SplayNode** s; 51 int top, n; 52 53 LinkCutTree() { } 54 LinkCutTree(int n, int m):n(n) { 55 pool = new SplayNode[(n + m + 1)]; 56 s = new SplayNode*[(n + m + 1)]; 57 } 58 59 void rotate(SplayNode* p) { 60 int d = p->which(), df = p->fa->which(); 61 SplayNode* fa = p->fa, *ffa = fa->fa, *ls = p->ch[d ^ 1]; 62 fa->ch[d] = ls, (ls) ? (ls->fa = fa) : (0); 63 p->fa = ffa, (~df) ? (ffa->ch[df] = p) : (0); 64 p->ch[d ^ 1] = fa, fa->fa = p; 65 fa->pushUp(), p->pushUp(); 66 } 67 68 void splay(SplayNode* p) { 69 SplayNode *np = p; 70 for (top = 0; s[++top] = np, !np->isroot(); np = np->fa); 71 for ( ; top; top--) 72 if (s[top]->rev) 73 s[top]->pushDown(); 74 for ( ; !p->isroot(); rotate(p)) 75 if (!p->fa->isroot()) 76 rotate((p->which() == p->fa->which()) ? (p->fa) : (p)); 77 } 78 79 void access(SplayNode *p) { 80 SplayNode* q = NULL; 81 while (p) { 82 splay(p); 83 p->ch[1] = q; 84 p->pushUp(); 85 q = p, p = p->fa; 86 } 87 } 88 89 void mkroot(SplayNode *p) { 90 access(p); 91 splay(p); 92 p->rev ^= 1; 93 } 94 95 void link(SplayNode* p, SplayNode* q) { 96 mkroot(q); 97 q->fa = p; 98 } 99 100 void cut(SplayNode* p, SplayNode* q) { 101 mkroot(p); 102 access(q); 103 p->ch[1] = q->fa = NULL; 104 p->pushUp(); 105 } 106 107 SplayNode* query(int u, int v) { 108 SplayNode* p = pool + u, *q = pool + v; 109 mkroot(p), access(q); 110 splay(p); 111 return p; 112 } 113 114 void link(int u, int v, int a, int b, int idx) { 115 SplayNode* p = pool + u, *q = pool + v, *es = pool + n + idx; 116 es->ea = es->ma = a, es->eb = es->mb = b, es->ib = es->idx = idx; 117 link(p, es), link(es, q); 118 } 119 120 void cut(int u, int v, int idx) { 121 SplayNode *p = pool + u, *q = pool + v, *es = pool + n + idx; 122 cut(p, es), cut(es, q); 123 } 124 125 void debugOut(SplayNode* p) { 126 if (!p) return; 127 fprintf(stderr, "%d (fa: %d, ea: %d, eb: %d, ma: %d, mb: %d, idx: %d, ib: %d, flag: %d) {", p - pool, (!p->fa) ? (0) : (p->fa - pool), p->ea, p->eb, p->ma, p->mb, p->idx, p->ib, p->rev); 128 debugOut(p->ch[0]); 129 fprintf(stderr, ", "); 130 debugOut(p->ch[1]); 131 fprintf(stderr, "}"); 132 } 133 134 void debugOut() { 135 fprintf(stderr, "--------------------\n"); 136 for (int i = 1; i <= 7; i++) 137 if (pool[i].isroot()) 138 debugOut(pool + i), fprintf(stderr, "\n"); 139 } 140 }LinkCutTree; 141 142 typedef class Edge { 143 public: 144 int u, v, a, b; 145 146 boolean operator < (Edge b) const { 147 return a < b.a; 148 } 149 }Edge; 150 151 int n, m; 152 int res = 211985; 153 int* f; 154 Edge* es; 155 LinkCutTree lct; 156 157 int find ( int x ) { 158 while ( x != f [x] ) x = f [x] = f [f [x]] ; 159 return x ; 160 } 161 162 inline void init() { 163 scanf("%d%d", &n, &m); 164 f = new int[(n + 1)]; 165 es = new Edge[(m + 1)]; 166 lct = LinkCutTree(n, m); 167 for (int i = 1; i <= n; i++) 168 f [i] = i ; 169 for (int i = 1; i <= m; i++) 170 scanf("%d%d%d%d", &es[i].u, &es[i].v, &es[i].a, &es[i].b); 171 } 172 <linkcuttree入门
鉴于最近写bzoj还有51nod都出现写不动的现象，决定学习一波厉害的算法/数据结构。linkcuttree：研究popoqqq那个神ppt。bzoj1036：维护access操作就可以了。#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>#include<q 查看详情
ac日记——模板linkcuttree洛谷p3690
【模板】LinkCutTree 思路： LCT模板； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn300005intn,m,val[maxn];inttop,ch[maxn][2],f[maxn],xr[maxn],q[maxn],rev[maxn];inlinevoidin(int&now 查看详情
p3690linkcuttree(动态树)
干脆整个LCT模板吧。缺个链上修改和子树操作，链上修改的话join(u,v)然后把vsplay到树根再打个标记就好。至于子树操作...以后有空的话再学(咕咕咕警告)1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintN=1e5+10;5intn,m,a[N],X... 查看详情
[]linkcuttree
坑了好久，本来打算就这样弃着，最近又被神秘力量驱使来学这个东西，过程很痛苦但最终还是知道它到底是啥了它可以用来对森林进行各种操作，为了快速地实现各种操作，我们要像树剖一样把整个森林剖成许多条链，每条链... 查看详情
luogu3690模板linkcuttree（动态树）
参考there和there#include<iostream>#include<cstdio>usingnamespacestd;intn,m,val[300005],ch[300005][2],sum[300005],fa[300005],uu,vv,opt;intrev[300005];voidpushDown(intx)if(rev[x])swap(ch[x][0 查看详情
luogup3690模板linkcuttree（动态树）
#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<cstdlib>#include<climits>#include<stack>#include<vector>#include<queue& 查看详情
linkcuttree（无图慎入）(代码片段)
类似树链剖分（其实直接记住就可以了），提前放代码1#include<cstdio>2#include<cstdlib>3#include<iostream>4#include<algorithm>5#include<cstring>6#include<climits>7#include<cmath>8#define 查看详情
luogu3690模板linkcuttree（动态树）
题目luogu3690硫硼作者想提醒大家，WA了TLE了RE了的，也许只是主函数写错了代码#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstdlib>#include<cstring>usingnamespacestd 查看详情
linkcuttree求最小生成树(代码片段)
对边建点，原图中的边转化为点的点-边的点-点的点于是用LCT维护连通关系，并支持查询最大值位置即可#include<bits/stdc++.h>usingnamespacestd;constintN=300005;intn,m,val[N],t1,t2,t3;namespacelct inttop,q[N],ch[N][2],fa[N],rev[N]; intmx[N]; inlin 查看详情
ural题目1553.cavesandtunnels（linkcuttree改动点权，求两点之间最大）
1553.CavesandTunnelsTimelimit:3.0secondMemorylimit:64MBAfterlandingonMarssurface,scientistsfoundastrangesystemofcavesconnectedbytunnels.Sotheybegantoresearchitusingremotecontrolledrobots.Itwasfoundout 查看详情
bzoj-2555substring后缀自动机+linkcuttree
2555:SubStringTimeLimit: 30Sec MemoryLimit: 512MBSubmit: 1936 Solved: 551[Submit][Status][Discuss]Description 懒得写背景了，给你一个字符串init，要求你支持两 查看详情
模板linkcuttree（动态树）
题目描述给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的... 查看详情
lct(linkcuttree)动态树(代码片段)
模板参考：https://blog.csdn.net/saramanda/article/details/55253627几个知识点：1、LCT中用Splay维护链，这些Splay叫做“辅助树“。辅助树以它上面每个节点的深度为关键字维护，就是辅助树中每个节点左儿子的深度小于当前节点的深度... 查看详情
linkcuttree动态树小结(代码片段)
动态树有些类似树链剖分+并查集的思想，是用splay维护的lct的根是动态的，"轻重链"也是动态的，所以并没有真正的轻重链动态树的操作核心是把你要把修改/询问/...等等一系列的操作的树链放到一个splay里，然后用splay根据相对... 查看详情
luogup3690模板linkcuttree（动态树）lct模板
P3690【模板】LinkCutTree（动态树）题目背景动态树题目描述给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和... 查看详情
bzoj-3779重组病毒linkcuttree+线段树+dfs序
3779:重组病毒TimeLimit: 20Sec MemoryLimit: 512MBSubmit: 224 Solved: 95[Submit][Status][Discuss]Description黑客们通过对已有的病毒反编译，将许多不同的病毒重组，并重新编译出了新型的重组病毒。这种病毒的繁殖和... 查看详情
linkcuttree
//知识点:LCT/*By:Luckyblock*/#include<cstdio>#include<ctype.h>#include<algorithm>#definels(t[x].son[0])#definers(t[x].son[1])constintkMaxn=1e5+10;//=============================================================structLink_Cut_Tree_Nodeintson[2],fa;intxr,rev;t[kMaxn];intn,m,val[kMa... 查看详情
洛谷3690：模板linkcuttree——题解(代码片段)
https://www.luogu.org/problemnew/show/P3690给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。1：... 查看详情