https://www.luogu.com.cn/problem/P10658
显然，一个边双内的点可以全部在一起，也就是可以缩成一个点
此时我们可以用LCT来维护，正常的连边显然，当要缩点时就把这点链提取出来，然后把整棵splay遍历一遍，搞一起即可
要拿个并查集维护实际对应点。
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCALd#define debug(...) fprintf(stdout, ##__VA_ARGS__)#define debag(...) fprintf(stderr, ##__VA_ARGS__)#else#define debug(...) void(0)#define debag(...) void(0)#endif
//#define int long long#ifdef nLOCAL
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#else int read() { long long x; scanf("%lld", &x); return (int)x; }
#endif
#define Z(x) (x)*(x)#define pb push_back#define fi first#define se second//#define M
//#define mo
#define N 300100int n, m, i, j, k, T;
int mp[N], a[N], A[N]; int F(int x) {
// debug("ka sai find Fa %lld %lld\n", x, mp[x]); if(mp[x] == x) return mp[x]; return mp[x] = F(mp[x]);
}namespace LCT {
#define ls(k) (son[k][0])#define rs(k) (son[k][1])int son[N][2], s[N], rev[N], f[N]; int fa(int x) { return F(f[x]); }void push_up(int k) {s[k] = s[ls(k)] + s[rs(k)] + a[k]; }void push_down(int k) {if(rev[k]) {swap(ls(k), rs(k)); if(ls(k)) rev[ls(k)] ^= 1; if(rs(k)) rev[rs(k)] ^= 1; rev[k] = 0; }}int zh(int x) {return rs(fa(x)) == x; }bool isRoot(int x) {if(!fa(x)) return true; return ls(fa(x)) != x && rs(fa(x)) != x; }void Rotate(int x) {
// debug("In Rotate\n"); int y = fa(x), z = fa(y); int k = zh(x), w = son[x][k ^ 1]; if(z && !isRoot(y)) son[z][zh(y)] = x; if(w) f[w] = y, son[y][k] = w; else son[y][k] = 0; f[x] = z; f[y] = x; son[x][k ^ 1] = y; push_up(y); push_up(x); push_up(z);
// debug("End Rotate\n"); }void Splay(int x) {stack<int>sta; sta.push(x); for(int y = x; !isRoot(y); y = fa(y)) sta.push(fa(y)); while(!sta.empty()) push_down(sta.top()), sta.pop(); while(!isRoot(x)) {int y = fa(x);
// debag("ka zai Splay"); if(!isRoot(y)) {if(zh(x) == zh(y)) Rotate(y); else Rotate(x); }Rotate(x);
// debag("End now splay"); }}void access(int x) {for(int y = 0; x; y = x, x = fa(x)) {
// debug("%lld ===> %lld \n", y, x); Splay(x); rs(x) = y; push_up(x); }}void makeRoot(int x) {
// debug("makeRoot(%lld)\n", x); access(x);
// debug("makeRoot(%lld)\n", x); Splay(x); rev[x] ^= 1; }int findRoot(int x) {Splay(x); while(push_down(x), ls(x)) x = ls(x); Splay(x); return x; }bool check(int x, int y) {
// debug("&&"); makeRoot(x); access(y);
// debug("$$ [%lld]%lld\n", x, findRoot(y)); return findRoot(y) == x; }void Link(int x, int y) {
// debug("[]]]]]]] Link %lld %lld\n", x, y); makeRoot(x); f[x] = y; }void add(int x, int k) {makeRoot(x); Splay(x); a[x] += k; s[x] += k; }void dfs(int x, int rt) {
// debug("dfsing(%lld)[%lld %lld] %lld\n", x, ls(x), rs(x), rt); mp[x] = rt; if(x != rt) a[rt] += a[x]; if(ls(x)) dfs(ls(x), rt); if(rs(x)) dfs(rs(x), rt); son[x][0] = son[x][1] = 0; }void Combine(int rt) {queue<int>q; q.push(rt); while(!q.empty()) {int x = q.front(); q.pop(); mp[x] = rt; if(x != rt) a[rt] += a[x]; if(ls(x)) q.push(ls(x)); if(rs(x)) q.push(rs(x)); son[x][0] = son[x][1] = 0; }s[rt] = a[rt]; son[rt][0] = son[rt][1] = 0; }void print() {#ifdef LOCALfor(int i = 1; i <= n; ++i) if(mp[i] == i)debug("%lld : %lld(%lld) [%lld %lld] %lld %lld\n", i, fa(i), (int)isRoot(i), ls(i), rs(i), a[i], s[i]); debug("================\n"); #endif}
}signed main()
{#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);#endif
// srand(time(NULL));
// T=read();
// while(T--) {
//
// }n = read(); m = read(); for(i = 1; i <= n; ++i) mp[i] = i; for(i = 1; i <= n; ++i) k = read(), LCT :: add(i, k), A[i] = k; for(i = 1; i <= m; ++i) {int op = read(), u, v;
// debag("===== %lld\n", i); if(op == 1) {u = read(); v = read(); u = F(u); v = F(v); if(u == v) continue;
// debug("Want to know %lld %lld\n", u, v); if(!LCT :: check(u, v)) LCT :: Link(u, v); else {
// debug("Try to comb %lld %lld\n", u, v); LCT :: makeRoot(u); LCT :: access(v); LCT :: Splay(u); LCT :: Combine(u); }}if(op == 2) {u = read(); k = read(); j = k - A[u]; A[u] = k; u = F(u); LCT :: add(u, j); }if(op == 3) {u = read(); v = read(); u = F(u); v = F(v);
// debug("qry(%lld %lld)\n", u, v); if(!LCT :: check(u, v)) { printf("-1\n"); continue; }LCT :: makeRoot(u); LCT :: access(v);
// LCT :: print(); LCT :: Splay(v); printf("%d\n", LCT :: s[v]); }
// LCT :: print(); }return 0;
}