題目描述

某校開展了同學們喜聞樂見的陽光長跑活動。為了能“為祖國健康工作五十年”，同學們紛紛離開寢室，離開教室，離開實驗室，到操場參加3000米長跑運動。一時間操場上熙熙攘攘，摩肩接踵，盛況空前。
　　為了讓同學們更好地監督自己，學校推行了刷卡機制。
　　學校中有n個地點，用1到n的整數表示，每個地點設有若干個刷卡機。
　　有以下三類事件：
　　1、修建了一條連接A地點和B地點的跑道。
　　2、A點的刷卡機臺數變為了B。
　　3、進行了一次長跑。問一個同學從A出發，最后到達B最多可以刷卡多少次。具體的要求如下：
　　當同學到達一個地點時，他可以在這里的每一臺刷卡機上都刷卡。但每臺刷卡機只能刷卡一次，即使多次到達同一地點也不能多次刷卡。
　　為了安全起見，每條跑道都需要設定一個方向，這條跑道只能按照這個方向單向通行。最多的刷卡次數即為在任意設定跑道方向，按照任意路徑從A地點到B地點能刷卡的最多次數。

題解

我們可以想一下題目說的一條合法路徑指的是什么，從一個點到另一個點，中間的路和環都可以走。

所以有一個想法，如果圖是靜態的，我們可以先邊雙縮點，然后倍增一下就好了。

但這個圖是動態的。所以我們用一個LCT來維護這個過程。

如果我們有一條邊連接的兩個點原來就是聯通的，我們可以把這條鏈縮成一個點，怎么縮呢，先把鏈拿出來，然后把這條鏈上的所有點都指向splay的頂端，然后把頂端的點和其他的點斷開，然后這個LCT中只有某些點的father是不對的，所以在訪問father的時候要find一下。

注意每次遍歷時都要pushdown

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #define ls tr[x][0] #define rs tr[x][1] #define father find(fa[x]) #define N 150009 using namespace std; int bcj[N],f[N],tr[N][2],fa[N],size[N],val[N],n,m,v[N]; bool rev[N]; inline int rd(){int x=0;char c=getchar();bool f=0;while(!isdigit(c)){if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } int find(int x){return f[x]=f[x]==x?x:find(f[x]);} int fd(int x){return bcj[x]=bcj[x]==x?x:fd(bcj[x]);} inline bool ge(int x){return tr[father][1]==x;} inline bool isroot(int x){return tr[father][1]!=x&&tr[father][0]!=x;} inline void pushup(int x){size[x]=size[ls]+size[rs]+val[x];} inline void pushdown(int x){if(rev[x]){rev[ls]^=1;rev[rs]^=1;rev[x]^=1;swap(ls,rs);}} inline void _pushdown(int x){if(!isroot(x))_pushdown(father);pushdown(x);} inline void rotate(int x){int y=father,o=ge(x);tr[y][o]=tr[x][o^1];fa[tr[y][o]]=y;if(!isroot(y))tr[find(fa[y])][ge(y)]=x;fa[x]=fa[y];//!!!!fa[y]=x;tr[x][o^1]=y;pushup(y);pushup(x); } inline void splay(int x){_pushdown(x);while(!isroot(x)){int y=father;if(isroot(y))rotate(x);else rotate(ge(y)==ge(x)?y:x),rotate(x);} } inline void access(int x){for(int y=0;x;y=x,x=father)splay(x),tr[x][1]=y,pushup(x);} inline void makeroot(int x){access(x);splay(x);rev[x]^=1;} inline void split(int x,int y){makeroot(x);access(y);splay(y);} inline void link(int x,int y){makeroot(x);fa[x]=y;} void dfs(int x,int rt){f[x]=rt;pushdown(x);////!!!!!!if(ls)dfs(ls,rt);if(rs)dfs(rs,rt); } int main(){n=rd();m=rd();int opt,x,y;for(int i=1;i<=n;++i)f[i]=i,v[i]=val[i]=rd(),bcj[i]=i;for(int i=1;i<=m;++i){opt=rd();x=rd();y=rd();if(opt==1){x=find(x);y=find(y);if(x==y)continue;int tx=fd(x),ty=fd(y);if(tx!=ty){bcj[tx]=ty;link(x,y);}else{split(x,y);dfs(y,y);val[y]+=size[tr[y][0]];tr[y][0]=0;pushup(y);}}else if(opt==2){int cha=y-v[x];v[x]=y;x=find(x);access(x);splay(x);val[x]+=cha;pushup(x);}else{x=find(x);y=find(y);if(fd(x)!=fd(y)){printf("-1\n");continue;}split(x,y);printf("%d\n",size[y]);}}return 0; }

?

轉載于:https://www.cnblogs.com/ZH-comld/p/10206802.html

總結

以上是生活随笔為你收集整理的bzoj3959(LCT)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。