Link Cut Tree 学习笔记
说在前边
最近补 CF 碰见一道 LCT ，就打算学习一下这个东西。。。顺便复习一下 splay。
具体算法及实现
P3690 【模板】Link Cut Tree （动态树）
题目：给定n个点以及每个点的权值，要你处理接下来的m个操作。操作有4种。操作从0到3编号。点从1到n编号。
0：后接两个整数(x，y)，代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。
1：后接两个整数(x，y)，代表连接x到y，若x到y已经联通则无需连接。
2：后接两个整数(x，y)，代表删除边(x，y)，不保证边(x，y)存在。
3：后接两个整数(x，y)，代表将点x上的权值变成y。
做法：模板
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cctype>
typedef long long ll;
const int N = 300010;
const int inf = 0x3f3f3f3f;
template<class T> inline void read(T &x) {
x = 0; char c = getchar(); T f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}
x *= f;
}
using namespace std;
class LCT {
private :
struct Node {
int ch[2], fa, rev, sum, w;
} T[N];
int st[N];
#define lc T[p].ch[0]
#define rc T[p].ch[1]
#define pa T[p].fa
inline int LR(int p) { return T[pa].ch[1] == p; }
inline int isR(int p) { return T[pa].ch[0] != p && T[pa].ch[1] != p; }
inline void PushUp(int p) { T[p].sum = T[lc].sum ^ T[rc].sum ^ T[p].w; }
inline void Pushr(int p) { T[p].rev ^= 1; swap(lc, rc); }
inline void PushDown(int p) {
if(T[p].rev) {
if(lc) Pushr(lc);
if(rc) Pushr(rc);
T[p].rev = 0;
}
}
inline void rotate(int p) {
int f=T[p].fa, g=T[f].fa, c=LR(p);
if(!isR(f)) T[g].ch[LR(f)]=p; T[p].fa=g;
T[f].ch[c] = T[p].ch[c^1]; T[T[f].ch[c]].fa=f;
T[p].ch[c^1] = f; T[f].fa=p;
PushUp(f); PushUp(p);
}
inline void splay(int p) {
int y=p,z=0; st[++z]=y;
while(!isR(y)) st[++z]=y=T[y].fa;
while(z) PushDown(st[z--]);
while(!isR(p)) {
y=T[p].fa;z=T[y].fa;
if(!isR(y)) rotate((T[y].ch[0]==p)^(T[z].ch[0]==y)?p:y);
rotate(p);
}
PushUp(p);
}
inline void access(int p) {
for(int y = 0; p; p = T[y = p].fa)
splay(p), rc = y, PushUp(p);
}
inline void makeR(int p) {
access(p); splay(p); Pushr(p);
}
int findR(int p) {
access(p); splay(p);
while(lc) PushDown(p), p = lc;
splay(p);
return p;
}
public :
inline void split(int x, int y) {
makeR(x); access(y); splay(y);
}
inline void Link(int x, int y) {
makeR(x);
if(findR(y)!=x)T[x].fa=y;
}
inline void Cut(int x, int y) {
makeR(x);
if(findR(y) == x && T[y].fa == x && !T[y].ch[0]) {
T[y].fa = T[x].ch[1] = 0; PushUp(x);
}
}
inline int getSum(int p) { return T[p].sum; }
inline void setW(int p, int v) { splay(p);T[p].w = v;PushUp(p); }
} tree;
int n, q, opt, u, v;
int main() {
read(n), read(q);
for(int i = 1; i <= n; ++i) read(v), tree.setW(i, v);
while(q--) {
read(opt), read(u), read(v);
if(opt == 0) tree.split(u, v), printf("%d
",tree.getSum(v));
else if(opt == 1) tree.Link(u, v);
else if(opt == 2) tree.Cut(u, v);
else if(opt == 3) tree.setW(u, v);
}
}
CodeForces 1137F
题意：给定一棵n点树。设第i个点当前编号为(p_i)。已知一种游戏，每次删除叶子节点中编号最小的那个节点，而节点(v)在一次游戏中被删除的时间为(Ti(v))。有(m)组询问，三种操作：1. (up ~v)将 (v) 点标号改为(1 + max(p_1,p_2,...,p_n)) 2. (when ~v)询问 (Ti(v)) 3.(compare ~u~v), 比较(Ti(u)), (Ti(v))。
做法：首先，操作3可以转化为操作2。现在，假设我们已经知道当前这棵树每个节点的(Ti)，那么当进行(up)操作时，这棵树的(Ti)会怎么变化？测试几组数据可以知道，每次只有原本的最大值，与新的最大值路径上的(Ti)会发生重编号，而这条链之外的节点的(Ti)相对大小没有改变。
为了操作方便我们用编号最大的点作为当前的根节点，考虑如何询问。我们定义(mxp(v))为(v)子树中最大的点的编号，对于一个节点(v)和一个节点(u)，如果(mxp(v) < mxp(u))，(v)一定先于(u)删除，因为在删除(mxp(u))之前一定已经删除了(mxp(v))而删除了(mxp(v))之后一定会继续删除，直到删除(v)。对于一个点(u)所有满足(mxp(v) < mxp(u)) 的(v) 一定先于他删除。如果(mxp(v) = mxp(u)) ，出现这种情况当且仅当(u)和(v)在一条指向根的路径上，那么由于根节点的编号最大，我们一定会先删除深度比较深的点。所以形式化的答案是
现在整理一下，我们要维护什么：每个点子树中的最大编号，深度信息，编号小于(v)的点的数目，编号为(v)的点中(dep)小于(d)的数目，要支持把编号最大点提到根的位置。
涉及到提根这个操作，所以想到使用(LCT)解决。每个辅助树的节点中除了常规的部分，维护(mxp)和子树的大小(sz)，而同时因为(LCT)的性质，其中每个(splay)中都是按照深度排序。再利用一个树状数组，维护编号小于(v)的点的数目。
初始化部分，我们(dfs)这棵树，求出每个点的父亲，同时我们将所有的点按照(mxp)连成一条条实链，顺便计算(sz)，以及在树状数组中更新。
对于询问操作(when ~v)，答案就是小于等于(mxp(v))的(mxp(u))的数量，减去深度小于(v)的(mxp)相同的点的数量。对于第一部分直接在树状数组中查询，第二部分利用(splay)的按深度排序的性质，我们(splay(v))将(v)旋到根上，此时它的左子树的(sz)就是我们要的。
对于修改操作(up ~v)，我们令原先最大的点为(u), (access(v)) 同时将所有v到u路径上的点的编号改为(mxp(u))，把(v)旋到根，再翻转这条链，此时(v)已经是整颗树的根了，但是此时的(v)的编号还没有修改，我们把(u)和它的右儿子断开重新给他打上新的标记即可。
这个过程中要注意，打上标记后及时(pushdown)，子节点修改后，及时(pushup)。
ps: 这题从复习(splay)，学习(LCT)，到看懂题解花了3天时间。参考了很多ac代码。。。
Code
#include <bits/stdc++.h>
#define pb push_back
typedef long long ll;
const int N = 200010;
template<class T> inline void read(T &x) {
x = 0; char c = getchar(); T f = 1;
while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
while(isdigit(c)) {x = x * 10 + c - '0'; c = getchar();}
x *= f;
}
using namespace std;
class BIT {
int n, a[N << 1];
public :
void init(int _) {
n = _;
}
void add(int p, int val) {
for(int i = p; i <= n; i += (i&(-i))) a[i] += val;
}
int ask(int p) { int ans = 0;
for(int i = p; i; i -= (i&(-i))) ans += a[i];
return ans;
}
} B;
struct Node {
int ch[2], fa, rev, sz, w, tag;
} T[N];
#define lc T[p].ch[0]
#define rc T[p].ch[1]
#define pa T[p].fa
inline int LR(int p) { return T[pa].ch[1] == p; }
inline int isR(int p) { return T[pa].ch[0] != p && T[pa].ch[1] != p; }
inline void PushUp(int p) { T[p].sz = T[lc].sz + T[rc].sz + 1; }
inline void Pushr(int p) { T[p].rev ^= 1; swap(lc, rc); }
inline void PushDown(int p) {
if(T[p].rev) {
if(lc) Pushr(lc);
if(rc) Pushr(rc);
T[p].rev = 0;
}
if(T[p].tag) {
T[lc].tag = T[lc].w = T[p].tag;
T[rc].tag = T[rc].w = T[p].tag;
T[p].tag = 0;
}
}
inline void rotate(int p) {
int f=T[p].fa, g=T[f].fa, c=LR(p);
if(!isR(f)) T[g].ch[LR(f)]=p; T[p].fa=g;
T[f].ch[c] = T[p].ch[c^1]; T[T[f].ch[c]].fa=f;
T[p].ch[c^1] = f; T[f].fa=p;
PushUp(f); PushUp(p);
}
inline void splay(int p) {
static int st[N];
int y=p,z=0; st[++z]=y;
while(!isR(y)) st[++z]=y=T[y].fa;
while(z) PushDown(st[z--]);
while(!isR(p)) {
y=T[p].fa;z=T[y].fa;
if(!isR(y)) rotate((T[y].ch[0]==p)^(T[z].ch[0]==y)?p:y);
rotate(p);
}
}
inline void access(int p, int ti) {
for(int y = 0; p; p = T[y = p].fa) {
splay(p); // splay 到顶
T[p].ch[1] = 0; // 断掉比他深的点
PushUp(p); // **
// update
B.add(T[p].w, -T[p].sz);
T[p].tag = T[p].w = ti;
B.add(T[p].w, T[p].sz);
T[p].ch[1] = y;// 右儿子接到上一层splay的根上
PushUp(p); // **
}
}
int n, q, u, v;
char opt[11];
vector<int> G[N];
void dfs(int u) {
T[u].w = u;
for(int v: G[u]) if(v != T[u].fa) {
T[v].fa = u; dfs(v);
T[u].w = max(T[u].w, T[v].w);
}
for(int v: G[u]) if(v != T[u].fa && T[u].w == T[v].w) {
T[u].ch[1] = v;
T[u].sz = T[v].sz + 1;
}
B.add(T[u].w, 1);
}
int qry(int p) {
splay(p); PushDown(p);
return B.ask(T[p].w) - T[lc].sz;
}
int main() {
#ifdef RRRR_wys
freopen("in.txt","r",stdin);
#endif
read(n), read(q);
B.init(n+q+2);
for(int i = 2; i <= n; ++i)
read(u), read(v), G[u].pb(v), G[v].pb(u);
for(int i = 1; i <= n; ++i) T[i].sz = 1;
dfs(n); int TT = n;
while(q--) {
scanf(" %s",opt);
if(opt[0] == 'u') {
read(v);
// MakeRoot
access(v, TT);
splay(v);
T[v].rev ^= 1; swap(T[v].ch[0], T[v].ch[1]);
PushDown(v);
// update
B.add(T[v].w, -1); // ***
T[v].ch[1] = 0; // 断右儿子
T[v].w = T[v].tag = ++ TT; // 重新标号
T[v].sz = 1; // 计算sz
B.add(T[v].w, 1);
}
else if(opt[0] == 'w') {
read(v);
printf("%d
", qry(v));
}
else {
read(u), read(v);
printf("%d
", (qry(u) < qry(v) ? u : v) );
}
}
}