BZOJ 2791 Poi2012 Rendezvous 倍增LCA

题目大意：给定一棵内向森林，多次给定两个点a和b，求点对(x,y)满足：

1.从a出发走x步和从b出发走y步会到达同一个点

2.在1的基础上如果有多解，那么要求max(x,y)最小

3.在1和2的基础上如果有多解，那么要求min(x,y)最小

4.如果在1、2、3的基础上仍有多解，那么要求x>=y

因此那个x>=y是用来省掉SPJ的，不是题目要求- -

容易发现：

如果a和b不在同一棵内向树上，显然无解，否则一定有解

定义根为从一个点出发能走到的第一个环上点，如果a和b的根相同，则到达LCA是最优的

否则到达的点一定是a的根和b的根中的一个，两种情况都计算一下，取最优解即可

《倍增LCA万年写不对系列》

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define M 500500 using namespace std; int n,q,T; int a[M],v[M],on_ring[M],pos[M],size[M]; int fa[M][20],dpt[M],root[M]; void DFS(int x) { v[x]=T; if(v[a[x]]==T) { int i,temp=1; for(i=x;temp==1||i!=x;i=a[i],temp++) on_ring[i]=T,pos[i]=temp,root[i]=i; size[T]=temp-1; return ; } if(!v[a[x]]) DFS(a[x]); if(!on_ring[x]) { fa[x][0]=a[x]; dpt[x]=dpt[a[x]]+1; root[x]=root[a[x]]; } } int LCA(int x,int y) { int j; if(dpt[x]
      
       =dpt[y]) x=fa[x][j]; if(x==y) return x; for(j=19;~j;j--) if(fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j]; return fa[x][0]; } int Distance(int x,int y,int p) { return (y-x+p)%p; } void Solve(int x,int y) { if(on_ring[root[x]]!=on_ring[root[y]]) { printf("%d %d\n",-1,-1); return ; } if(root[x]==root[y]) { int lca=LCA(x,y); printf("%d %d\n",dpt[x]-dpt[lca],dpt[y]-dpt[lca]); return ; } int fx=root[x],fy=root[y]; int x1=dpt[x]+Distance(pos[fx],pos[fy],size[on_ring[fx]]),y1=dpt[y]; int x2=dpt[x],y2=dpt[y]+Distance(pos[fy],pos[fx],size[on_ring[fy]]); if(max(x1,y1)!=max(x2,y2)) { if(max(x1,y1)
       
        >n>>q; for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;i<=n;i++) if(!v[i]) ++T,DFS(i); for(j=1;j<=19;j++) for(i=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; for(i=1;i<=q;i++) { scanf("%d%d",&x,&y); Solve(x,y); } return 0; }