【BZOJ2959】长跑
Description
某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”，同学们纷纷离开寝室，离开教室，离开实验室，到操场参加3000米长跑运动。一时间操场上熙熙攘攘，摩肩接踵，盛况空前。
为了让同学们更好地监督自己，学校推行了刷卡机制。 学校中有n个地点，用1到n的整数表示，每个地点设有若干个刷卡机。 有以下三类事件： 1、修建了一条连接A地点和B地点的跑道。 2、A点的刷卡机台数变为了B。 3、进行了一次长跑。问一个同学从A出发，最后到达B最多可以刷卡多少次。具体的要求如下： 当同学到达一个地点时，他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次，即使多次到达同一地点也不能多次刷卡。 为了安全起见，每条跑道都需要设定一个方向，这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向，按照任意路径从A地点到B地点能刷卡的最多次数。Input
输入的第一行包含两个正整数n,m，表示地点的个数和操作的个数。 第二行包含n个非负整数，其中第i个数为第个地点最开始刷卡机的台数。 接下来有m行，每行包含三个非负整数P,A,B，P为事件类型，A,B为事件的两个参数。 最初所有地点之间都没有跑道。 每行相邻的两个数之间均用一个空格隔开。表示地点编号的数均在1到n之间，每个地点的刷卡机台数始终不超过10000，P=1,2,3。
Output
输出的行数等于第3类事件的个数，每行表示一个第3类事件。如果该情况下存在一种设定跑道方向的方案和路径的方案，可以到达，则输出最多可以刷卡的次数。如果A不能到达B，则输出-1。
题解：如果是一棵树，那么直接求两点间路径即可；如果形成了环，那么整个环是可以一起走的，相当于环变成了一个点，我们可以在LCT的过程中维护一个并查集来实现这个过程。
缩环的具体方法：先access+splay使a,b在同一棵splay里，然后DFS整棵splay，将所有点与根的并查集合并，然后将根的儿子清空。这相当于我们直接删除了这些点，但是其它点的fa也会产生变化，所以我们每次调用fa的时候都在并查集中find一下就行了。
注意：判断两点是否连通要再开一个并查集！不能用findroot！
#include#include #include using namespace std;const int maxn=150010;int n,m,tot;int F[maxn],f[maxn],fa[maxn],rev[maxn],ch[2][maxn],s[maxn],v[maxn],V[maxn];int find(int x){ return (f[x]==x)?x:(f[x]=find(f[x]));}int Find(int x){ return (F[x]==x)?x:(F[x]=Find(F[x]));}bool isr(int x) {return ch[0][find(fa[x])]!=x&&ch[1][find(fa[x])]!=x;}void pushup(int x){ s[x]=s[ch[0][x]]+s[ch[1][x]]+v[x];}void pushdown(int x){ if(rev[x]) { swap(ch[0][x],ch[1][x]); if(ch[0][x]) rev[ch[0][x]]^=1; if(ch[1][x]) rev[ch[1][x]]^=1; rev[x]=0; }}void updata(int x){ if(!isr(x)) updata(find(fa[x])); pushdown(x);}void rotate(int x){ int y=find(fa[x]),z=find(fa[y]),d=(x==ch[1][y]); if(!isr(y)) ch[y==ch[1][z]][z]=x; fa[x]=z,fa[y]=x,ch[d][y]=ch[d^1][x]; if(ch[d^1][x]) fa[ch[d^1][x]]=y; ch[d^1][x]=y; pushup(y),pushup(x);}void splay(int x){ updata(x); while(!isr(x)) { int y=find(fa[x]),z=find(fa[y]); if(!isr(y)) { if((x==ch[0][y])^(y==ch[0][z])) rotate(x); else rotate(y); } rotate(x); }}void access(int x){ for(int y=0;x;splay(x),ch[1][x]=y,pushup(x),y=x,x=find(fa[x]));}void maker(int x){ access(x),splay(x),rev[x]^=1;}void dfs(int x,int y){ f[x]=y; pushdown(x); if(ch[0][x]) dfs(ch[0][x],y); if(ch[1][x]) dfs(ch[1][x],y);}int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();} while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret*f;}int main(){ n=rd(),m=rd(); int i,a,b,c,d; for(i=1;i<=n;i++) s[i]=V[i]=v[i]=rd(),F[i]=f[i]=i; for(i=1;i<=m;i++) { c=rd(),a=rd(),b=rd(); if(c==1) { a=find(a),b=find(b); if(a==b) continue; maker(a),access(b),splay(b); if(Find(a)!=Find(b)) fa[a]=b,F[F[a]]=F[b]; else v[b]=s[b],dfs(b,b),ch[0][b]=ch[1][b]=0; } if(c==2) d=a,a=find(a),splay(a),v[a]+=b-V[d],V[d]=b,pushup(a); if(c==3) { a=find(a),b=find(b); if(Find(a)!=Find(b)) printf("-1\n"); else maker(a),access(b),splay(b),printf("%d\n",s[b]); } } return 0;}//9 31 10 20 30 40 50 60 70 80 90 3 1 2 1 1 3 1 1 2 1 8 9 1 2 4 1 2 5 1 4 6 1 4 7 3 1 8 3 8 8 1 8 9 3 8 8 3 7 5 3 7 3 1 4 1 3 7 5 3 7 3 1 5 7 3 6 5 3 3 6 1 2 4 1 5 5 3 3 6 2 8 180 3 8 8 2 9 190 3 9 9 2 5 150 3 3 6 2 1 210 3 3 6