思路
看到题目即可想到使用LCT
然而我们发现，只维护点之间的关系是不行的，因为图上可能会构成环
因此我们将边双缩点，发现缩完点后原图变成了森林
因此就可以直接用LCT做了
接下来，我们考虑如何在边双缩点的同时维护LCT
首先，我们对于每一个点都要再维护该点所在边双的权值和
另外，LCT的操作中，凡是涉及到父节点的，都必须要访问父节点所在的边双
因此，对于操作1，如果两个点当前不处于一个连通块中，就把他们link起来
否则的话，就把他们丢到一个边双中，具体操作就是先将 (x) 到 (y) 的路径split出来，修改完y的信息后，再让路径上所有的节点都归入到 (y) 的边双中
对于修改的话，直接将 (x) splay上来，再直接修改信息即可，但需要注意的是修改信息时哪里需要使用边双，哪里不需要
对于查询的话，如果不在同一连通块中输出-1，否则split出来后直接输出
然而，使用findroot查询连通块效率太低，因此我们在存储边双的并查集外再开了一个并查集用于判连通性
代码如下
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 150000 + 10;
struct node {
int ch[2], p;
int sum, size, w;
int revFlag;
} nod[N];
int fa[N];
int find(int x) {
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int fa2[N];
int find2(int x) {
if(fa2[x]==x)return x;
return fa2[x]=find2(fa2[x]);
}
inline void pushup(int x) {
nod[x].sum = nod[nod[x].ch[0]].sum + nod[nod[x].ch[1]].sum + nod[x].size;
}
inline void pushdown(int x) {
if (nod[x].revFlag) {
swap(nod[x].ch[0],nod[x].ch[1]) ;
nod[nod[x].ch[0]].revFlag^=1;
nod[nod[x].ch[1]].revFlag^=1;
nod[x].revFlag = 0;
}
}
inline int type(int x) {
if(nod[find(nod[x].p)].ch[0] == x) return 0;
if(nod[find(nod[x].p)].ch[1] == x) return 1;
return -1;
}
inline void rotate(int x) {
int y=find(nod[x].p), z=find(nod[y].p), typo=type(x);
if(type(y)!=-1) {
nod[z].ch[type(y)]=x;
}
nod[x].p=z;
nod[y].ch[typo] = nod[x].ch[typo^1], nod[nod[x].ch[typo^1]].p = y;
nod[x].ch[typo^1] = y;
nod[y].p=x;
pushup(y);
pushup(x);
}
inline void down(int x) {
if (type(x) != -1) down(find(nod[x].p));
pushdown(x);
}
inline void splay(int x) {
down(x);
while (type(x) != -1) {
int y=find(nod[x].p),z=find(nod[y].p);
if (type(y) != -1) {
if (type(y)==type(x))rotate(y);
else rotate(x);
}
rotate(x);
}
}
inline void access(int x) {
int y=0;
while(x) {
splay(x);
nod[x].ch[1]=y;
pushup(x);
y=x,x=find(nod[x].p);
}
}
inline void makeroot(int x) {
access(x);
splay(x);
nod[x].revFlag ^= 1;
}
inline int findroot(int x) {
access(x);
splay(x);
while (nod[x].ch[0]) pushdown(x), x = nod[x].ch[0];
return x;
}
inline void split(int x,int y) {
makeroot(x);
access(y);
splay(y);
}
inline void link(int x,int y) {
makeroot(x);
nod[x].p=y;
}
inline void dfs(int x,int y) {
fa[x]=y;
pushdown(x);
if(nod[x].ch[0])dfs(nod[x].ch[0],y);
if(nod[x].ch[1])dfs(nod[x].ch[1],y);
}
int n, q, op, x, y;
int main() {
freopen("run.in","r",stdin);
freopen("run.out","w",stdout);
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) {
scanf("%d", &nod[i].w);
nod[i].sum=nod[i].size=nod[i].w;
fa[i]=fa2[i]=i;
}
while (q--) {
scanf("%d%d%d", &op, &x, &y);
if (op == 1) {
x=find(x),y=find(y);
if(x==y)continue;
if (find2(x) != find2(y)) {
link(x, y);
fa2[fa2[x]]=fa2[y];
} else {
split(x,y);
nod[y].size=nod[y].sum;
dfs(y,y);
nod[y].ch[0]=0;
}
}
if (op == 2) {
int fx=find(x);
splay(fx);
nod[fx].size += y-nod[x].w;
nod[fx].sum += y-nod[x].w;
nod[x].w = y;
}
if (op == 3) {
x=find(x),y=find(y);
if (find2(x)!= find2(y)) {
printf("-1
");
} else {
split(x, y);
printf("%d
", nod[y].sum);
}
}
// for(int i=1; i<=n; i++) {
// printf("%d %d %d %d %d %d %d %d
",fa[i],nod[i].p,nod[i].ch[0],nod[i].ch[1],nod[i].size,nod[i].sum,nod[i].revFlag,nod[i].w);
// }
}
}