题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5967
题解：通过LCT来维护基环内向树
由于这是一个有向图，所以所有树都有根
对于可能形成环的边，我们可以发现一定是从树的根连出去的，我们只需要维护LCT的时候标记这个树根有没有连接到内部的边，在每次cut操作的时候判断能不能把这条边加进来，如果可以就进行link操作，注意可能有自环，要特殊处理。其实还是个延时标记的思想啊，貌似这个题，见过的人就能秒啊。。。确实挺好写的。
代码：
#include<bits/stdc++.h> using namespace std; const int MAXN=2e5+5; namespace LCT { int ch[MAXN][2],pre[MAXN],key[MAXN]; bool rt[MAXN]; void Rotate(int x) { int y=pre[x],kind=ch[y][1]==x; ch[y][kind]=ch[x][!kind]; pre[ch[y][kind]]=y; pre[x]=pre[y]; pre[y]=x; ch[x][!kind]=y; if(rt[y]) rt[y]=false,rt[x]=true; else ch[pre[x]][ch[pre[x]][1]==y]=x; } void Splay(int r) { while(!rt[r]) { int f=pre[r],ff=pre[f]; if(rt[f]) Rotate(r); else if((ch[ff][1]==f)==(ch[f][1]==r)) Rotate(f),Rotate(r); else Rotate(r),Rotate(r); } } int Access(int x) { int y=0; for(;x;x=pre[y=x]) { Splay(x); rt[ch[x][1]]=true,rt[ch[x][1]=y]=false; } return y; } //判断是否是同根(真实的树，非splay) bool judge(int u,int v) { while(pre[u]) u=pre[u]; while(pre[v]) v=pre[v]; return u==v; } //使r成为它所在的树的根 void mroot(int r) { Access(r); Splay(r); } void link(int u,int v) { if(judge(u,v)) { key[u]=v; return; } mroot(u); pre[u]=v; } int findroot(int u) { Access(u); Splay(u); while(ch[u][0]) u=ch[u][0]; return u; } //使u成为u所在树的根，并且v和它父亲的边断开 void cut(int u) { int r=findroot(u); mroot(u); pre[ch[u][0]]=0; pre[u]=0; rt[ch[u][0]]=true; ch[u][0]=0; if(key[r]&&!judge(r,key[r])) { link(r,key[r]); key[r]=0; } if(r==u) key[r]=0; } void init(int n) { for(int i=0;i<=n;i++) { pre[i]=0; ch[i][0]=ch[i][1]=0; rt[i]=true; key[i]=0; } } } using namespace LCT; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,m; while(~scanf("%d%d",&n,&m)) { init(n); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); if(x) link(i,x); } for(int i=1;i<=m;i++) { int op; scanf("%d",&op); if(op==1) { int x,y; scanf("%d%d",&x,&y); cut(x); if(y) link(x,y); } else { int x,r; scanf("%d",&x); r=findroot(x); if(key[r]) puts("-1"); else printf("%d\n",r); } } } return 0; }
