本文主要是介绍HDU 5967 小R与手机 （LCT），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：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;elsech[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);elseRotate(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");elseprintf("%d\n",r);}}}return 0;
}
这篇关于HDU 5967 小R与手机 （LCT）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
