Link-Cut-Tree 一日通

我写的东西都是为了补充这些资料，所以先浏览下这些 ：

QTREE解法的一些研究 - Yang Zhe 一个论文，自己搜吧
Kuangbin 写的这个模板题的代码
语言还挺生动的。。
Yang Zhe 论文注解版

然后。。如果你发现你学不会。。就看代码。。就能学会了。。。

改造 Splay

哎。。感觉真的没什么讲的，主要是 access 的实现还有 rot 和 fa 的变异。
access 大家都能看懂了。。

fa 和 splay 里的 fa 不一样了。一颗 splay 的根也可以有 fa，代表这棵 splay 维护的路径的最上端节点的fa。（这样做的主要原因是方便access)
原来我们认为一个节点没有 fa 就是根，现在都有 fa 了怎么办呢？就再开一个bool rt[]表示它是不是根
为了区别和 splay 的不同，我把 fa 改叫 pre 了
然后我们需要 splay 里的代码 把判根的方法从 fa[]是否空 改到 rt[]真假 (这点主要影响splay函数)，还要维护新fa的性质。

举个例子，rot

inline void rot(int o) {
	int d = gd(o), x = pre[o];
  //这段是把 o 替换到 x 原来的位置
	pre[o] = pre[x];//不管 x 是不是根，它的父亲都将成为 o 的父亲
	if (rt[x]) rt[x] = 0, rt[o] = 1; //如果 x 是根，就不改 pre[x] 的儿子，因为 ch[pre[x]][0/1] 都不是 x，因为他们都不在一颗 splay 里
	else ch[pre[x]][gd(x)] = o; //x 不是根，按普通 splay 一样连下
  //处理孩子之类的
	lk(ch[o][d^1], x, d);
	lk(x, o, d^1);
	up(x);
	up(o);
}

splay

除了到达根的条件，其他不变。

从子节点更新

然后你懂的，splay 一般要 up。
up 的时机？
Splay 的结构改变的时候。
实际上只存在一种情况, Splay 的结构会改动：ch[] 改动的时候。
也就是 ch[]改动 <-当且仅当-> 调用 up

为什么pre[]和up没这种关系我就不证了。如果理解lct的话就明白，不理解的话我解释一下这点反而会更迷？

然后写的时候注意下改ch[]就要up就行, 也就是accees，cut和传统项目splay。

access

没啥难懂的。自己去看 kuangbin 代码吧。注意access里的每次pre都是跳到上一个链而不是在splay中移动就行。

把边也转化成点，见水管局长

通过抄标程学算法（逃
这种比较复杂的数据结构啊，说说真的是没啥用，详细描述过程也没用，还是看代码和写代码吧。
就像 splay 这种东西，没什么可讲的，就是看谁写的比较精妙。

魔鬼在细节中

//1180-OTOCI
#include <cstdio>
#include <algorithm>
const int N = 3e4 + 10;
int n, m, pre[N], ch[N][2], w[N], s[N];
bool rev[N];
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void lk(int x, int y, int d) {
	if (x) pre[x] = y;
	if (y) ch[y][d] = x;
}
inline bool rt(int o) {return ch[pre[o]][gd(o)] != o;}
inline void mkr(int o) {if (o) std::swap(ch[o][1], ch[o][0]), rev[o] ^= 1;}
inline void down(int o) {if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;}
inline void up(int o) {
	s[o] = w[o] + s[ch[o][0]] + s[ch[o][1]];
}
inline void rot(int o) {
	int x = pre[o], d = gd(o);
	pre[o] = pre[x];
	if (!rt(x)) ch[pre[x]][gd(x)] = o;
	lk(ch[o][d^1], x, d);
	lk(x, o, d^1);
	up(x), up(o);
}
void clear(int o) {
	if (!rt(o)) clear(pre[o]);
	down(o);
}
inline void splay(int o) {
	for (clear(o); !rt(o); rot(o))
		if (!rt(pre[o])) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
inline void access(int o) {
	for (int x = 0; o; o = pre[x = o])
		splay(o), ch[o][1] = x, up(o);
}
inline void mkrt(int o) {access(o), splay(o), mkr(o);}
int find(int o) {return pre[o] ? find(pre[o]) : o;}
inline void link(int u, int v){mkrt(u),pre[u] = v;}
char cmd[20];
int main() {
//	freopen("input", "r", stdin);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", w + i), up(i);
	scanf("%d", &m);
	while (m--) {
		int u, v;
		scanf("%s%d%d", cmd, &u, &v);
		if (cmd[0] == 'b') {
			if (find(u) == find(v)) puts("no");
			else {
				puts("yes");
				link(u, v);
			}
		}
		else if (cmd[0] == 'p') splay(u), w[u] = v, up(u);
		else if (cmd[0] == 'e') {
			if (find(u) == find(v)) {
				mkrt(u), access(v), splay(v);
				printf("%d\n", s[v]);
			}
			else puts("impossible");
		}
	}
}

//2049-SDOI2008-Cave
#include <cstdio>
#include <algorithm>
#include <cassert>
#define file(x) "sdoi2008_cave." #x
const int N = 1e4 + 10;
int n, m, pre[N], ch[N][2];
bool rt[N], rev[N];
char cmd[20];
inline void mkr(int o) {
	if (!o) return;
	rev[o] ^= 1;
	std::swap(ch[o][0], ch[o][1]);
}
inline void down(int o) {
	if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;
}
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void lk(int x, int y, int d) {
	if (x) pre[x] = y;
	if (y) ch[y][d] = x;
}
inline void rot(int o) {
	int d = gd(o), x = pre[o];
	if (rt[x]) pre[o] = pre[x], rt[x] = 0, rt[o] = 1;
	else lk(o, pre[x], gd(x));
	lk(ch[o][d^1], x, d);
	lk(x, o, d^1);
//	up(x), up(o);
}
void clear(int o) {
	if (!rt[o]) clear(pre[o]);
	down(o);
}
void splay(int o) {
	for (clear(o); !rt[o]; rot(o))
		if (!rt[pre[o]]) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
void access(int o) {
	for (int x = 0; o;) {
		splay(o);
		rt[ch[o][1]] = 1, rt[ch[o][1] = x] = 0;
		o = pre[x = o];
	}
}
inline void mkrt(int o) {
	access(o);
	splay(o);
	mkr(o);
}
inline void cut(int u, int v) {
	mkrt(u);
	access(v);
	splay(v);
	pre[ch[v][0]] = pre[v], rt[ch[v][0]] = 1;
	pre[v] = ch[v][0] = 0;
}
inline void link(int u, int v) {
	mkrt(u);
	pre[u] = v;
}
inline bool query(int u, int v) {
	while (pre[u]) u = pre[u];
	while (pre[v]) v = pre[v];
	return u == v;
}
int main() {
//	freopen(file(in), "r", stdin);
//	freopen(file(out), "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 0; i <= n; i++) rt[i] = 1;
	while (m--) {
		int x, y;
		scanf("%s%d%d", cmd, &x, &y);
		if (cmd[0] == 'Q') puts(query(x, y) ? "Yes" : "No");
		else if (cmd[0] == 'C') link(x, y);
		else cut(x, y);
	}
}

//3091 城市旅行
#include <cstdio>
#include <algorithm>
#include <vector>
const int N = 5e4 + 10;
typedef long long ll;
int n, m, pre[N], ch[N][2];
bool rt[N], rev[N];
ll ad[N], w[N], s[N], sz[N], ls[N], rs[N], e[N];
inline void up(int o) {
	s[o] = w[o] + s[ch[o][0]] + s[ch[o][1]];
	sz[o] = 1 + sz[ch[o][0]] + sz[ch[o][1]];
	ls[o] = ls[ch[o][0]] + (sz[ch[o][0]] + 1)*s[ch[o][1]] + ls[ch[o][1]] + w[o]*(sz[ch[o][0]] + 1);
	rs[o] = rs[ch[o][1]] + (sz[ch[o][1]] + 1)*s[ch[o][0]] + rs[ch[o][0]] + w[o]*(sz[ch[o][1]] + 1);
	e[o] = e[ch[o][0]] + e[ch[o][1]] + (sz[ch[o][0]] + 1)*rs[ch[o][1]] + (sz[ch[o][1]] + 1)*ls[ch[o][0]] + (sz[ch[o][0]] + 1)*(sz[ch[o][1]] + 1)*w[o];
}
inline void mkad(int o, ll x) {
	if (o)  {
		s[o] += x*sz[o],
		w[o] += x,
		ad[o] += x;
		ll u = sz[o]*(sz[o] + 1)*x/2;
		ls[o] += u, rs[o] += u;
		e[o] += x*sz[o]*(sz[o] + 1)*(sz[o] + 2)/6;
	}
}
inline void mkr(int o) {if (o) std::swap(ch[o][0], ch[o][1]), std::swap(ls[o], rs[o]), rev[o] ^= 1;}
inline void down(int o) {
	if (ad[o]) mkad(ch[o][0], ad[o]), mkad(ch[o][1], ad[o]), ad[o] = 0;
	if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;
}
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void lk(int x, int y, int d) {
	if (x) pre[x] = y;
	if (y) ch[y][d] = x;
}
inline void rot(int o) {
	int d = gd(o), x = pre[o];
	pre[o] = pre[x];
	if (rt[x]) rt[x] = 0, rt[o] = 1;
	else ch[pre[x]][gd(x)] = o;
	lk(ch[o][d^1], x, d);
	lk(x, o, d^1);
	up(x);
	up(o);
}
inline void clear(int o) {
	if (!rt[o]) clear(pre[o]);
	down(o);
}
inline void splay(int o) {
	for (clear(o); !rt[o]; rot(o))
		if (!rt[pre[o]]) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
inline void access(int o) {
	for (int x = 0; o; ) {
		splay(o);
		rt[ch[o][1]] = 1, rt[ch[o][1] = x] = 0;
		up(o);
		o = pre[x = o];
	}
}
inline void mkrt(int o) {
	access(o);
	splay(o);
	mkr(o);
}
inline int find(int u) {for(;pre[u]; u = pre[u]); return u;}
inline void cut(int u, int v) {
	if (find(u) != find(v)) return;
	mkrt(u);
	access(v);
	splay(v);
	if (ch[v][0] == u && ch[u][1] == 0) {
		pre[ch[v][0]] = pre[v], rt[ch[v][0]] = 1;
		pre[v] = ch[v][0] = 0;
		up(v);
	}
}
inline void link(int u, int v) {
	if (find(u) == find(v)) return;
	mkrt(u);
	pre[u] = v;
}
ll gcd(ll a, ll b) {return b ? gcd(b, a%b) : a;}
std::vector<int> to[N];
void dfs(int u, int fa) {
	for (int i = 0; i < (int)to[u].size(); i++) if (to[u][i] != fa) pre[to[u][i]] = u, dfs(to[u][i], u);
}
int main() {
//	freopen("input", "r", stdin);
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%lld", w + i), rt[i] = 1, up(i);
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		to[u].push_back(v);
		to[v].push_back(u);
	}
	dfs(1, 0);
	while (m--) {
		int t, u, v;
		scanf("%d%d%d", &t, &u, &v);
		if (t == 1) cut(u, v);
		else if (t == 2) link(u, v);
		else if (t == 3) {
			int d;
			scanf("%d", &d);
			if (find(u) != find(v)) continue;
			mkrt(u);
			access(v);
			splay(v);
			mkad(v, d);
		}
		else {
			if (find(u) != find(v)) {
				puts("-1");
				continue;
			}
			mkrt(u);
			access(v);
			splay(v);
			ll c = e[v], m = sz[v]*(sz[v] + 1)/2, d = gcd(c, m);
			printf("%lld/%lld\n", c/d, m/d);
		}
	}
}

//2631-tree
#include <cstdio>
#include <vector>
#include <algorithm>
typedef unsigned int ll;
const int N = 1e5 + 10;
const ll M = 51061;
std::vector<int> to[N];
int n, m, pre[N], ch[N][2];
ll sz[N], ad[N], mu[N], w[N], s[N];
bool rt[N], rev[N];
void dfs(int u, int fa) {
	pre[u] = fa;
	for (int i = 0; i < (int)to[u].size(); i++) if (to[u][i] != fa) dfs(to[u][i], u);
}
inline void up(int o) {
	sz[o] = 1 + sz[ch[o][0]] + sz[ch[o][1]];
	s[o] = (w[o] + s[ch[o][0]] + s[ch[o][1]])%M;
}
inline void mkr(int o) {
	rev[o] ^= 1, std::swap(ch[o][0], ch[o][1]);
}
inline void mkad(int o, ll x) {
	if (o) {
		s[o] = (s[o] + sz[o]*x)%M;
		w[o] = (w[o] + x)%M;
		ad[o] = (ad[o] + x)%M;
	}
}
inline void mkmu(int o, ll x) {
	if (o) {
		s[o] = x*s[o]%M;
		w[o] = x*w[o]%M;
		ad[o] = ad[o]*x%M;
		mu[o] = mu[o]*x%M;
	}
}
inline void down(int o) {
	if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;
	if (mu[o] != 1) mkmu(ch[o][0], mu[o]), mkmu(ch[o][1], mu[o]), mu[o] = 1;
	if (ad[o]) mkad(ch[o][0], ad[o]), mkad(ch[o][1], ad[o]), ad[o] = 0;
}
inline void lk(int x, int y, int d) {
	if (x) pre[x] = y;
	if (y) ch[y][d] = x;
}
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void rot(int o) {
	int x = pre[o], d = gd(o);
	pre[o] = pre[x];
	if (rt[x]) rt[x] = 0, rt[o] = 1;
	else ch[pre[x]][gd(x)] = o;
	lk(ch[o][d^1], x, d);
	lk(x, o, d^1);
	up(x);
	up(o);
}
void clear(int o) {
	if (!rt[o]) clear(pre[o]);
	down(o);
}
inline void splay(int o) {
	for (clear(o); !rt[o]; rot(o))
		if (!rt[pre[o]]) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
inline void access(int o) {
	for (int x = 0; o;) {
		splay(o);
		rt[ch[o][1]] = 1, rt[ch[o][1] = x] = 0;
		up(o);
		o = pre[x = o];
	}
}
inline void mkrt(int u) {
	access(u);
	splay(u);
	mkr(u);
}
inline void link(int u, int v) {
	mkrt(u);
	pre[u] = v;
}
inline void cut(int u, int v) {
	mkrt(u);
	access(v);
	splay(v);
	pre[ch[v][0]] = pre[v], rt[ch[v][0]] = 1;
	pre[v] = ch[v][0] = 0;
	up(v);
}
inline void select(int u, int v) {
	mkrt(u);
	access(v);
	splay(v);
}
char cmd[5];
int main() {
//	freopen("input", "r", stdin);
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		rt[i] = w[i] = mu[i] = 1;
		up(i);
		int u, v;scanf("%d%d", &u ,&v);
		to[u].push_back(v);
		to[v].push_back(u);
	}
	rt[n] = w[n] = mu[n] = 1;
	up(n);
	dfs(1, 0);
	while (m--) {
		int u0, v0, c, u1, v1;
		scanf("%s%d%d", cmd, &u0, &v0);
		if (cmd[0] == '+') {
			scanf("%d", &c);
			select(u0, v0);
			mkad(v0, c);
		}
		else if (cmd[0] == '-') {
			scanf("%d%d", &u1, &v1);
			cut(u0, v0);
			link(u1, v1);
		}
		else if (cmd[0] == '*') {
			scanf("%d", &c);
			select(u0, v0);
			mkmu(v0, c);
		}
		else if (cmd[0] == '/') {
			select(u0, v0);
			printf("%u\n", s[v0]);
		}
	}
}

//水管局长
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <map>
#define file(x) "tube."#x
#define f(x) re
typedef long long ll;
const int M = 1e6 + 10, N = 1e5 +10 +M, Q = 1e5 + 10, V = 1e5 + 10;
namespace I {
	const int L = 1 << 15 | 1;
	char *s,*t, buf[L];
	inline char gc() {
		if (s == t) t = (s = buf) + fread(buf, 1, L, stdin);
		return *s++;
	}
	inline int gi() {
		int ch = gc(), x = 0;
		while (!isdigit(ch)) ch = gc();
		while (isdigit(ch)) x = x*10 + ch - '0', ch = gc();
		return x;
	}
}using I::gi;
int n, m, q, ch[N][2], pre[N], hed[N], nxt[M << 2], w[N], mxi[N], st[M << 2], th[M];
bool rt[N], rev[N];
struct EDGE{int u, v, w;
	bool rm, in;
	bool operator<(const EDGE& b)const {
		return w < b.w;
	}
	inline void rd() {
		u = gi(), v = gi(), w = gi();
	}
}e[M], qu[Q];
bool cmp2(int i, int j) {return e[i].u < e[j].u || (e[i].u == e[j].u && e[i].v < e[j].v);}
inline ll zip(ll u, ll v) {
	if (u > v) std::swap(u, v);
	return u*V + v;
}
inline void _add(int u, int v){
	static int sz = 0;
	st[++sz] = v;
	nxt[sz] = hed[u], hed[u] = sz;
}
inline void add(int u, int v){
	_add(u, v), _add(v, u);
}
namespace Kruskal {
	int p[N];
	int find(int x) {return p[x] == x ? x : p[x] = find(p[x]);}
	void solve() {
		for (int i = 1; i <= m; i++) p[i] = i;
		std::sort(e + 1, e + 1 + m);
		for (int i = 1; i <= m; i++) if (!e[i].rm) {
			int u = find(e[i].u), v = find(e[i].v);
			if (u == v) continue;
			p[u] = v;
			e[i].in = 1;
		}
	}
}
inline void mkr(int o) {if(o) std::swap(ch[o][0], ch[o][1]), rev[o] ^= 1;}
inline void down(int o) {if (rev[o]) mkr(ch[o][0]), mkr(ch[o][1]), rev[o] = 0;}
inline void up(int o) {
	mxi[o] = o > n ? o : 0;
	for (int i = 0; i < 2; i++) if (w[mxi[ch[o][i]]] > w[mxi[o]]) mxi[o] = mxi[ch[o][i]];
}
inline int gd(int o) {return ch[pre[o]][1] == o;}
inline void lk(int x, int y, int d) {
	if (x) pre[x] = y;
	if (y) ch[y][d] = x;
}
//inline bool rt(int o) {return ch[pre[o]][0] == o || ch[pre[o]][1] == o;}
inline void rot(int o) {
	int x = pre[o], d = gd(o);
	pre[o] = pre[x];
	if (rt[x]) rt[x] = 0, rt[o] = 1;
	else ch[pre[x]][gd(x)] = o;
	lk(ch[o][d^1], x, d);
	lk(x, o, d^1);
	up(x);
	up(o);
}
void clear(int o) {
	if (!rt[o]) clear(pre[o]);
	down(o);
}
inline void splay(int o) {
	for (clear(o); !rt[o]; rot(o))
		if (!rt[pre[o]]) rot(gd(o) == gd(pre[o]) ? pre[o] : o);
}
inline void access(int o) {
	for (int x = 0; o; ) {
		splay(o);
		rt[ch[o][1]] = 1, rt[ch[o][1] = x] = 0;
		up(o);
		o = pre[x = o];
	}
}
inline void mkrt(int o) {
	access(o);
	splay(o);
	mkr(o);
}
inline void link(int u, int v) {mkrt(u), pre[u] = v;}
inline void cut(int u, int v) {
	mkrt(u);
	access(v);
	splay(v);
	pre[u] = pre[v], rt[u] = 1;
	pre[v] = ch[v][0] = 0;
	up(v);
}
void dfs(int u, int fa) {
	pre[u] = fa;
	rt[u] = 1;
	up(u);
	for (int g = hed[u], v; v = st[g]; g = nxt[g]) if (v != fa) dfs(v, u);
}
inline int query(int u, int v) {
	mkrt(u),access(v), splay(v);
	return mxi[v];
}
int find(int u, int v) {
	if (u > v) std::swap(u, v);
	e[m + 1].u = u, e[m + 1].v = v;
	int p = std::lower_bound(th + 1, th + 1 + m, m + 1, cmp2) - th;
	return th[p];
}
int main() {
//	freopen("input", "r", stdin);
//	freopen(file(in), "r", stdin);
//	freopen(file(out), "w", stdout);
	n = gi(), m = gi(), q = gi();
	for (int i = 1; i <= m; i++) e[i].rd(), th[i] = i;
	std::sort(th + 1, th + 1 + m, cmp2);
	for (int i = 1; i <= q; i++) {
		qu[i].rd();
		if (qu[i].u == 2) {
			e[find(qu[i].v, qu[i].w)].rm = 1;
		}
	}
	Kruskal::solve();
	std::sort(th + 1, th + 1 + m, cmp2);
	for (int i = 1; i <= m; i++) {
		if (e[i].in) {
			add(e[i].u, n + i);
			add(e[i].v, n + i);
		}
		w[n + i] = e[i].w;
	}
	dfs(1, 0);
	for (int i = q; i; i--) if (qu[i].u == 1) qu[i].v = w[query(qu[i].v, qu[i].w)];
	else {
		int x = query(qu[i].v, qu[i].w), id = find(qu[i].v, qu[i].w);
		if (w[n + id] < w[x]) {
			cut(x, e[x - n].u);
			cut(x, e[x - n].v);
			link(n + id, qu[i].v);
			link(n + id, qu[i].w);
		}
	}
	for (int i = 1; i <= q; i++) if (qu[i].u == 1) printf("%d\n", qu[i].v);
}

后注：
这些代码也有点时间了，有些地方写的很naive，比如水管局长的cut。
推荐阅读第一个代码，不开数组维护rt的版本。简单很多。
然后水管局长的cut可以splayx然后更简单。