原理 https://blog.csdn.net/weixin_30872337/article/details/98507056 这篇文章对原理和实现都讲的挺好的。
正确性 这个不是很好理解。一棵树中，LCT用一个splaytree表示一条链，按照结点的深度顺序存储，所以无论splaytree怎么旋转，这条链内节点的相对位置不变，即原始树中的链没动，只是splaytree转了。不同的链由虚边相连，虚边只有可能变成实边，不会改变链接的结点，所以已经链接好的两个结点也不会在旋转中发生改变。 所以LCT中的一系列，除cut，link外，其他操作不会改变已经连好的结构。
实现
#include<cstdio> using namespace std; const int maxn = 1e5 + 5; int fa[maxn], c[maxn][2], rev[maxn], que[maxn]; inline bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; } void rotate(int u) { bool k = c[fa[u]][1] == u; int x = fa[u], y = fa[x]; fa[u] = y; if (!isroot(x)) c[y][c[y][1] == x] = u; c[x][k] = c[u][!k]; fa[c[u][!k]] = x; c[u][!k] = x; fa[x] = u; } void pushdown(int x) { if (rev[x]) { if (c[x][0]) { swap(c[c[x][0]][0], c[c[x][0]][1]); rev[c[x][0]] ^= 1; } if (c[x][1]) { swap(c[c[x][1]][0], c[c[x][1]][1]); rev[c[x][1]] ^= 1; } rev[x] = 0; } } void splay(int u) { int top = 0; que[++top] = u; for (int uu=u; !isroot(uu); uu = fa[uu]) que[++top] = fa[uu]; while (top) pushdown(que[top--]); int x, y; while (!isroot(u)) { x = fa[u], y = fa[x]; if (!isroot(x)) c[y][0] == x ^ c[x][0] == u ? rotate(u) : rotate(x); rotate(u); } } void access(int u) { int rc = 0; while (u) { splay(u); c[u][1] = rc; rc = u; u = fa[u]; } } void make_root(int u) { access(u); splay(u); rev[u] ^= 1; swap(c[u][0], c[u][1]); } int findroot(int u) { access(u); splay(u); while (c[u][0]) { pushdown(c[u][0]); u = c[u][0]; } splay(u); //这里不知道为什么要spaly return u; } void link(int x, int y) { make_root(x); fa[x] = y; } void cut(int x, int y) { make_root(x); access(y); splay(y); c[y][0] = fa[x] = 0; } bool check(int x, int y) { make_root(x); return findroot(y) == x; }在findroot操作中，最后一个splay不知道为什么，但是不加的话有的题会超时。网上有的模板加有的不加 比如下面这个题。
几个题
2852: 我大哥 很简单的一个题，但是发现在findroot操作中，最后一个splay不加就会超时，想不明白。
#include<iostream> #include<limits.h> #include<algorithm> #include<functional> #include<cstdio> using namespace std; const int maxn = 1e5 + 5; int fa[maxn], c[maxn][2], rev[maxn], que[maxn]; int root[maxn]; inline bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; } void rotate(int u) { bool k = c[fa[u]][1] == u; int x = fa[u], y = fa[x]; fa[u] = y; if (!isroot(x)) c[y][c[y][1] == x] = u; c[x][k] = c[u][!k]; fa[c[u][!k]] = x; c[u][!k] = x; fa[x] = u; } void pushdown(int x) { if (rev[x]) { if (c[x][0]) { swap(c[c[x][0]][0], c[c[x][0]][1]); rev[c[x][0]] ^= 1; } if (c[x][1]) { swap(c[c[x][1]][0], c[c[x][1]][1]); rev[c[x][1]] ^= 1; } rev[x] = 0; } } void splay(int u) { int top = 0; que[++top] = u; for (int uu=u; !isroot(uu); uu = fa[uu]) que[++top] = fa[uu]; while (top) pushdown(que[top--]); int x, y; while (!isroot(u)) { x = fa[u], y = fa[x]; if (!isroot(x)) c[y][0] == x ^ c[x][0] == u ? rotate(u) : rotate(x); rotate(u); } } void access(int u) { int rc = 0; while (u) { splay(u); c[u][1] = rc; rc = u; u = fa[u]; } } void make_root(int u) { access(u); splay(u); rev[u] ^= 1; swap(c[u][0], c[u][1]); } int findroot(int u) { access(u); splay(u); while (c[u][0]) { pushdown(c[u][0]); u = c[u][0]; } splay(u); return u; } void link(int x, int y) { make_root(x); fa[x] = y; } void cut(int x, int y) { make_root(x); access(y); splay(y); c[y][0] = fa[x] = 0; } bool check(int x, int y) { make_root(x); return findroot(y) == x; } int main() { char cmd[15]; int m, n; int x, y; scanf("%d%d", &m, &n); for (int i = 0; i < n; ++i) { scanf("%s%d%d", cmd, &x, &y); if (cmd[0] == 'c') { if (root[x]) cut(root[x], x); link(x, y); root[x] = y; } else { printf("%s\n", check(x, y) ? "Yes" : "No"); } } return 0; }P2590 [ZJOI2008]树的统计 加树边，求最大值，求和，没有删除操作，其实可以用树剖做。 注意点是要先初始化权重，再进行连边操作。
/* P2590 [ZJOI2008]树的统计 https://www.luogu.org/problem/P2590 */ #include<iostream> #include<limits.h> #include<algorithm> #include<functional> #include<cstdio> using namespace std; const int maxn = 1e5 + 5; int fa[maxn], c[maxn][2], rev[maxn], que[maxn], cnt[maxn], w[maxn], mx[maxn]; int xs[maxn], ys[maxn]; inline bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; } void up(int x) { mx[x] = max(max(mx[c[x][0]], mx[c[x][1]]), w[x]); cnt[x] = cnt[c[x][0]] + cnt[c[x][1]] + w[x]; } void rotate(int u) { bool k = c[fa[u]][1] == u; int x = fa[u], y = fa[x]; fa[u] = y; if (!isroot(x)) c[y][c[y][1] == x] = u; c[x][k] = c[u][!k]; fa[c[u][!k]] = x; c[u][!k] = x; fa[x] = u; up(x); up(u); } void pushdown(int x) { if (rev[x]) { if (c[x][0]) { swap(c[c[x][0]][0], c[c[x][0]][1]); rev[c[x][0]] ^= 1; } if (c[x][1]) { swap(c[c[x][1]][0], c[c[x][1]][1]); rev[c[x][1]] ^= 1; } rev[x] = 0; } } void splay(int u) { int top = 0; que[++top] = u; for (int uu=u; !isroot(uu); uu = fa[uu]) que[++top] = fa[uu]; while (top) pushdown(que[top--]); int x, y; while (!isroot(u)) { x = fa[u], y = fa[x]; if (!isroot(x)) c[y][0] == x ^ c[x][0] == u ? rotate(u) : rotate(x); rotate(u); } } void access(int u) { int rc = 0; while (u) { splay(u); c[u][1] = rc; up(u); rc = u; u = fa[u]; } } void make_root(int u) { access(u); splay(u); rev[u] ^= 1; swap(c[u][0], c[u][1]); } void link(int x, int y) { make_root(x); fa[x] = y; } void penguins(int u, int neww) { splay(u); w[u] = neww; up(u); } int getsum(int x, int y) { make_root(x); access(y); splay(x); return cnt[x]; } int getmax(int x, int y) { make_root(x); access(y); splay(x); return mx[x]; } int main() { int n, q, x, y; char cmd[15]; scanf("%d", &n); for (int i = 1; i < n; ++i) { scanf("%d%d", &xs[i], &ys[i]); } for (int i = 1; i <= n; ++i) { scanf("%d", &w[i]); cnt[i] = w[i]; mx[i] = w[i]; } for (int i = 1; i < n; ++i) { link(xs[i], ys[i]); } mx[0] = -50000; scanf("%d", &q); for (int i = 0; i < q; ++i) { scanf("%s %d %d", cmd, &x, &y); if (cmd[1] == 'M') printf("%d\n", getmax(x, y)); else if (cmd[1] == 'S') { printf("%d\n", getsum(x, y)); } else penguins(x, y); } return 0; }P2387 [NOI2014]魔法森林
一个图，可能有自环和重边，每条边两个权重A,B，要求是从点1到点n，找一条路径，这条路径中最大的A与最大的B之和最小。 思路是用并查集维护连通情况（LCT判断是否连通很慢）（只要连通1和n就可以），把所有边按照A从小到大排序，依次把每条边加入最小生成树中，如果这条边的两个点x,y之前未连接，直接加入。否则取出x，y之间B最大的那条边，如果B大于待加入的边的B，就删掉图中的边，加入新的边，不然就不加。 两个点是否连通用并查集，找权值B最大的边用LCT，加边的方式是把边作为一个点，加一条边link两次link（x，边）；link（边，y），所有点的权值为0。
正确性： 当前待加入的边的A肯定大于最小生成树中所有的边的A，如果待加入的边的B也大于取出的边B，那这条边肯定不用加。 如果当前的最小生成树还没有连通1和n，待加入的边又无法拓展新的点（因为构成了环路），那么肯定还需要加入更多的边才有可能连通1和n。假设刚好连通1到n时加入的边为k，那此时的输出就是k.A+图中最大的B，之前的A都不起作用，只有B起作用。所以A可以理解为一个定值，只能缩小B来减小答案。 (代码实现是按照B排序的)
#include<iostream> #include<limits.h> #include<algorithm> #include<functional> #include<cstdio> using namespace std; const int maxn = 2e5 + 5; int fa[maxn], c[maxn][2], rev[maxn], que[maxn], w[maxn], mx[maxn], uni[maxn]; struct edge { int x, y, a, b; bool operator<(edge &n) { return b < n.b; } }; edge es[maxn]; inline bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; } int cx(int x) { if (uni[x] != x) uni[x] = cx(uni[x]); return uni[x]; } void zm(int x, int y) { int r1 = cx(x), r2 = cx(y); if (r1 != r2) uni[r1] = r2; } void up(int x) { mx[x] = x; if (w[mx[c[x][0]]] > w[mx[x]]) mx[x] = mx[c[x][0]]; if (w[mx[c[x][1]]] > w[mx[x]]) mx[x] = mx[c[x][1]]; } void rotate(int u) { bool k = c[fa[u]][1] == u; int x = fa[u], y = fa[x]; fa[u] = y; if (!isroot(x)) c[y][c[y][1] == x] = u; c[x][k] = c[u][!k]; fa[c[u][!k]] = x; c[u][!k] = x; fa[x] = u; up(x); up(u); } void pushdown(int x) { if (rev[x]) { if (c[x][0]) { swap(c[c[x][0]][0], c[c[x][0]][1]); rev[c[x][0]] ^= 1; } if (c[x][1]) { swap(c[c[x][1]][0], c[c[x][1]][1]); rev[c[x][1]] ^= 1; } rev[x] = 0; } } void splay(int u) { int top = 0; que[++top] = u; for (int uu = u; !isroot(uu); uu = fa[uu]) que[++top] = fa[uu]; while (top) pushdown(que[top--]); int x, y; while (!isroot(u)) { x = fa[u], y = fa[x]; if (!isroot(x)) c[y][0] == x ^ c[x][0] == u ? rotate(u) : rotate(x); rotate(u); } } void access(int u) { int rc = 0; while (u) { splay(u); c[u][1] = rc; up(u); rc = u; u = fa[u]; } } void make_root(int u) { access(u); splay(u); rev[u] ^= 1; swap(c[u][0], c[u][1]); } void link(int x, int y) { make_root(x); fa[x] = y; } void cut(int x, int y) { make_root(x); access(y); splay(y); c[y][0] = fa[x] = 0; up(y); } int getmax(int x, int y) { make_root(x); access(y); splay(x); return mx[x]; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= m; ++i) { scanf("%d%d%d%d", &es[i].x, &es[i].y, &es[i].a, &es[i].b); } sort(es + 1, es + 1 + m); for (int i = n + 1; i <= n + m; ++i) w[i] = es[i - n].a; for (int i = 1; i <= n; ++i) uni[i] = i; for (int i = 1; i <= n + m; ++i) mx[i] = i; int x, y, a, b, u, v, k; int ans = INT_MAX; for (int i = 1; i <= m; ++i) { bool add = true; x = es[i].x, y = es[i].y; if (cx(x) == cx(y)) { k = getmax(x, y); if (w[k] > es[i].a) cut(es[k - n].x, k), cut(k, es[k - n].y); else add = false; } else zm(x, y); if (add) link(x, i + n); link(i + n, y); if (cx(1) == cx(n)) ans = min(ans, es[i].b + w[getmax(1, n)]); } if (ans < INT_MAX) printf("%d\n", ans); else printf("-1\n"); return 0; }P4219 [BJOI2014]大融合
一棵树找一条边切断，两棵子树size相乘。 需要维护每个结点对应的子树和，包括实边和虚边。 询问的时候makeroot一个结点，然后access，splay另一个结点，(s[y] - s[x]) * s[x]就是答案了，y是根节点，x是左结点。(si[x] + 1) * (si[y] + 1)也可以，si是存每个结点所有虚边对应的size和。
注意点：因为是要求子树的和，所以在link的时候要考虑向上更新。一定要先access并且splay才行，因为涉及到了虚边，所以需要更新到整棵树的根。实际上在access的时候，把一个结点连到父节点的右边时，父节点的总子节点数是不变的，相当于本来的右子树变成虚的，本来虚的变成了右子树。但如果link的时候没有向上更新，相当于父节点记录的虚子树结点个数比实际上的要少了，这样就不对了。
#include<iostream> #include<cstdio> using namespace std; const int maxn = 2e5 + 5; int fa[maxn], c[maxn][2], rev[maxn], que[maxn], s[maxn], si[maxn]; inline bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; } void up(int x) { s[x] = s[c[x][0]] + s[c[x][1]] + 1 + si[x]; } void rotate(int u) { bool k = c[fa[u]][1] == u; int x = fa[u], y = fa[x]; fa[u] = y; if (!isroot(x)) c[y][c[y][1] == x] = u; c[x][k] = c[u][!k]; fa[c[u][!k]] = x; c[u][!k] = x; fa[x] = u; up(x); up(u); } void pushdown(int x) { if (rev[x]) { if (c[x][0]) { swap(c[c[x][0]][0], c[c[x][0]][1]); rev[c[x][0]] ^= 1; } if (c[x][1]) { swap(c[c[x][1]][0], c[c[x][1]][1]); rev[c[x][1]] ^= 1; } rev[x] = 0; } } void splay(int u) { int top = 0; que[++top] = u; for (int uu = u; !isroot(uu); uu = fa[uu]) que[++top] = fa[uu]; while (top) pushdown(que[top--]); int x, y; while (!isroot(u)) { x = fa[u], y = fa[x]; if (!isroot(x)) c[y][0] == x ^ c[x][0] == u ? rotate(u) : rotate(x); rotate(u); } } void access(int u) { int rc = 0; while (u) { splay(u); si[u] += s[c[u][1]] - s[rc]; c[u][1] = rc; up(u);//如果初始化s全部为1的话就不用这个了。没有初始化的话s全是0， //单个结点link的时候make_root会调用access，把结点的s变成1。 rc = u; u = fa[u]; } } void make_root(int u) { access(u); splay(u); rev[u] ^= 1; swap(c[u][0], c[u][1]); } void link(int x, int y) { make_root(x); access(y); splay(y); fa[x] = y; si[y] += s[x]; up(y); } long long int getmax(int x, int y) { make_root(x); access(y); splay(y); //return (si[x] + 1)*(si[y] + 1); return (s[y] - s[x])*s[x]; } int main() { int n, m, x, y; scanf("%d%d", &n, &m); char cmd[4]; for (int i = 0; i < m; ++i) { scanf("%s%d%d", cmd, &x, &y); if (cmd[0] == 'A') link(x, y); else printf("%lld\n", getmax(x, y)); } return 0; }题目列表参考了https://blog.csdn.net/qq_36551189/article/details/79152612
