bzoj 2959: 长跑（LCT + 并查集 维护边双通）

对图跑一遍 tarjan，对边双通缩点得到一棵树，答案就是树上两点路径之间的点权和。

因为过程中有加边操作，考虑用 LCT 来维护边双通。

在加边时，若加入这条边没有形成环，则直接加边。若形成了环，则需要在 LCT 上进行暴力缩点。

考虑每个节点维护一个 $bel[u]$ 表示每个点所在的边双通， LCT 辅助树上只维护边双通的代表点，其它的点不维护到 splay 中（同属一个边双通的其它点并不会立刻完全删除，它们仍可能被某些 splay 的虚边连接，每次暴力修改这些虚边很麻烦，只有 $access$ 操作连接不同的 splay，考虑在做 $access$ 操作时用并查集直接跳到它们所在边双通的代表点，省去修改虚边的时间）。

由于整个过程有加边操作，$bel[u]$ 要用并查集维护，考虑如何维护使得 LCT 中只有边双通的代表点被维护在辅助树中：

如果维护的图是一棵树显然成立，当加一条边 $(x,y)$ 出现新的边双通时，更新 $(x,y)$ 路径上的点的 $bel[u]$ ，将其指向 $x$（或 $y$），这个过程依赖于暴力修改。修改 $x$ 的点权值，设为整个连通分量的权值和。最后将 $x$ 与 $x$ 的儿子节点断开，断开保证了在整棵辅助树中，同一个分量的点不会出现超过一个，这样保证了子树信息的正确性。

考虑 $access$ 操作 ：只有 $access$ 操作会修改 LCT 中 $splay$ 维护的点的集合，由于前面删了点，但没有修改全部虚边，如果 $x=f[x]$ 跳可能会将多个相同分量的点维护到同一棵 splay 中，因此要走并查集的边直接找到 $f[x]$ 对应的 边双通代表点：$x=find(f[x])$，因为在辅助树上不存在两个同分量的点，这个操作不会出现死循环。

整个LCT的过程就是对图的所有边双通缩点，将代表点维护到辅助树中，缩点的过程至多进行 $n$ 次，复杂度是均摊的，最终复杂度为 $O(n\log n)$，但常数特别大，在判连通性的地方用并查集而不用 findroot 可以减少点常数，因为缩点的关系辅助树上很多虚边没有修改，要注意用并查集查找所属的连通分量代表点。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
#define pii pair<int,int>
#define fir first
#define sec second
int n,m,res[maxn];
vector<int> g[maxn];
inline int read(){int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
struct LCT {				//用splay维护原森林的连通，用到了splay的操作以及数组 int ch[maxn][2];		//ch[u][0] 表示 左二子，ch[u][1] 表示右儿子int f[maxn];			//当前节点的父节点 int tag[maxn];			//翻转标记，乘标记，加标记 int top,sta[maxn],sz[maxn];int val[maxn],sum[maxn],v[maxn];	//v维护初始权值, val维护splay上的节点权值，sum维护子树和 int bel[maxn],p[maxn];					//belong 维护每个节点所属的连通块，因为过程中有加边，用并查集维护 inline bool get(int x) {return ch[findbel(f[x])][1] == x;}int findbel(int x) {return x == bel[x] ? x : bel[x] = findbel(bel[x]);}int find(int x) {return x == p[x] ? x : p[x] = find(p[x]);}void init() {memset(f,0,sizeof f);memset(ch,0,sizeof ch);memset(tag,0,sizeof tag);for (int i = 1; i <= maxn - 10; i++) sz[i] = 1, bel[i] = p[i] = i;}inline void pushup(int rt) {if (rt) {sz[rt] = 1; sum[rt] = val[rt];int ls = ch[rt][0], rs = ch[rt][1];if (ls) {sz[rt] += sz[ls];sum[rt] += sum[ls];}if (rs) {sz[rt] += sz[rs];sum[rt] += sum[rs];}}}inline void pushdown(int rt) {if (tag[rt]) {int ls = ch[rt][0], rs = ch[rt][1];if (ls) swap(ch[ls][0],ch[ls][1]), tag[ls] ^= 1;if (rs) swap(ch[rs][0],ch[rs][1]), tag[rs] ^= 1;tag[rt] = 0;}}inline bool isroot(int x) {int fx = findbel(f[x]);return (ch[fx][0] != x) && (ch[fx][1] != x);}inline void rotate(int x) {							//旋转操作，根据 x 在 f[x] 的哪一侧进行左旋和右旋 int old = findbel(f[x]), oldf = findbel(f[old]);int whichx = get(x);if(!isroot(old)) ch[oldf][ch[oldf][1] == old] = x;		//如果 old 不是根节点，就要修改 oldf 的子节点信息ch[old][whichx] = ch[x][whichx ^ 1];ch[x][whichx ^ 1] = old;f[ch[old][whichx]] = old;f[old] = x; f[x] = oldf;pushup(old); pushup(x); }inline void splay(int x) {								//将 x 旋到所在 splay 的根top = 0; sta[++top] = x;for (int i = x; !isroot(i); i = findbel(f[i])) sta[++top] = findbel(f[i]); //在 splay 中维护 下推标记 while(top) pushdown(sta[top--]);for(int fa = findbel(f[x]); !isroot(x); rotate(x), fa = findbel(f[x])) {	//再把x翻上来if(!isroot(fa))										//如果fa非根，且x 和 fa是同一侧，那么先翻转fa，否则先翻转x rotate((get(x) == get(fa)) ? fa : x);}}inline void access(int x) {					//access操作将x 到 根路径上的边修改为重边 int lst = 0;while(x > 0) {splay(x);ch[x][1] = lst;pushup(x);lst = x; x = findbel(f[x]);}}inline void dfs(int x,int y) {bel[x] = y;pushdown(x);if (ch[x][0]) dfs(ch[x][0],y);if (ch[x][1]) dfs(ch[x][1],y);}inline void move_to_root(int x) {			//将 x 移到 x 所在树的根（不是所在splay的根，所在splay只是一条重链） access(x); splay(x); tag[x] ^= 1; swap(ch[x][0],ch[x][1]);//将 x 移到 根之后 x 是深度最低的点，这条重链、这棵splay上所有点的深度颠倒，//所有的点的左子树的点应该到右子树，因此要翻转这棵splay的左右子树}inline void link(int x,int y) {move_to_root(x); f[x] = y; splay(x);}inline void cut(int x,int y) {move_to_root(x); access(y); splay(y); ch[y][0] = f[x] = 0;pushup(y);}
}tree;
int x,y,u,v,op;
int main() {n = read(); m = read();tree.init();for (int i = 1; i <= n; i++) {int v = read();tree.val[i] = tree.v[i] = tree.sum[i] = v;}while (m--) {op = read(); x = read(); y = read();if (op == 1) {int tx = tree.findbel(x), ty = tree.findbel(y);int fx = tree.find(tx), fy = tree.find(ty);if (tx != ty) {				//不在一个边双通里 if (fx != fy) {tree.link(tx,ty);	// 直接为边双通连边tree.p[fx] = fy;} else {tree.move_to_root(tx);tree.access(ty);tree.splay(ty);tree.val[ty] = tree.sum[ty];tree.dfs(ty,ty);tree.ch[ty][0] = 0;	//断掉子树，使得每个 splay 中一个连通分量只存在一个点，保证子树和的正确性//这个操作保证了多余的点不会出现在辅助树上 tree.pushup(ty); }}} else if (op == 2) {int tx = tree.findbel(x);tree.splay(tx);tree.val[tx] += y - tree.v[x];tree.sum[tx] += y - tree.v[x];tree.v[x] = y;} else {int tx = tree.findbel(x), ty = tree.findbel(y);if (tree.find(tx) != tree.find(ty)) puts("-1");else {tree.move_to_root(tx);tree.access(ty);tree.splay(ty);printf("%d\n",tree.sum[ty]);	}}}return 0;
}