Description:

学校中有 $N$ 个地点，用 $1$ 到 $N$ 的整数表示，每个地点设有若干个刷卡机。 有以下三类事件：

1、修建了一条连接 $A$ 地点和 $B$ 地点的跑道。

2、 $A$ 点的刷卡机台数变为了 $B$ 。

3、进行了一次长跑。

问一个同学从 $A$ 出发，最后到达 $B$ 最多可以刷卡多少次。具体的要求如下： 当同学到达一个地点时，他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次，即使多次到达同一地点也不能多次刷卡。 为了安全起见，每条跑道都需要设定一个方向，这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向，按照任意路径从A地点到B地点能刷卡的最多次数。

$ N \le 1.5\times10^5 $ $ M \le 5N $

Solution:

可以发现一个边双连通分量中的所有点都能通过合理调整边的方向取到，然后就变成了 $LCT$ 处理边双连通分量的常用套路，并查集维护递归缩点即可，注意用 $tot$ 表示当前这个点代表了多少个缩起来的点（包括他自己），在每次缩点时加上环的长度即可

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 150010

int a[MAXN];

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

struct node

{

	int c[2],fa,tot,siz;

	bool rev;

	node(){c[0] = c[1] = fa = 0;tot = siz = 1;rev = false;}

}t[MAXN];

void maintain(int k)

{

	t[k].siz = t[k].tot;

	if(t[k].c[0] != 0)t[k].siz += t[t[k].c[0]].siz;

	if(t[k].c[1] != 0)t[k].siz += t[t[k].c[1]].siz;

	return;

}

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void pushdown(int k){if(t[k].rev){t[t[k].c[0]].rev ^= 1;t[t[k].c[1]].rev ^= 1;swap(t[k].c[0],t[k].c[1]);t[k].rev = false;}return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx^1],y,fx);

	connect(y,x,fx^1);

	maintain(y);maintain(x);	

	return;

}

stack<int> s;

void splay(int x)

{

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

void access(int k){for(int i = 0;k != 0;i = k,k = t[k].fa = find(t[k].fa)){splay(k);t[k].c[1] = i;maintain(k);}return;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

void link(int x,int y){makeroot(x);makeroot(y);t[x].fa = y;return;}

int root(int x){access(x);splay(x);while(true){pushdown(x);if(t[x].c[0] != 0)x = t[x].c[0];else return x;}}

void remove(int k,int tp){if(k == 0)return;f[k] = tp;remove(t[k].c[0],tp);remove(t[k].c[1],tp);t[k].c[0] = t[k].c[1] = 0;return;}

void merge(int x,int y){if(x == y)return;if(root(x) != root(y))link(x,y);else{makeroot(x);access(y);splay(x);t[x].tot = t[x].siz;remove(x,x);}return;}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

		t[i].tot = t[i].siz = a[i];

	}

	for(int i = 1;i <= n;++i)f[i] = i;

	int x,y,k;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&k,&x,&y);

		if(k == 1)merge(find(x),find(y));

		if(k == 2){splay(find(x));t[find(x)].tot -= a[x];a[x] = y;t[find(x)].tot += a[x];maintain(find(x));}

		if(k == 3)

		{

			x = find(x);y = find(y);

			if(root(x) == root(y)){makeroot(x);access(y);splay(y);printf("%d\n",t[y].siz);}

			else puts("-1");

		}

	}

	return 0;

}