POI2012 Rendezvous
sol：
首先把连通块划分出来。
对于不在一个连通块的两点不能相会，否则必定能相会。
在一个连通块内的又需分情况考虑。
先把环给拎出来，则环上每个点挂着一棵子树（不算环上的点）。
如果两点在一棵子树，则直接求lca即可，路径唯一，二者步数也唯一。
如果两点不在一棵子树，则必然二者都需要先走到环上，
然后两点有两种方式可以相会，按照题目要求讨论即可。
细节有点多，仔细考虑清楚每一步该怎么写就好了。
尽量减少vector的直接调用，不然不开O2的情况下，常数巨大！
#include<bits/stdc++.h>
#define IL inline
#define RG register
#define DB double
#define LL long long
#define pb push_back
using namespace std;
IL int gi() {
RG int x=0,p=1; RG char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') p=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return x*p;
}
const int N=5e5+3;
vector<int> S[N],cir[N];
int n,m,num,top,tot,a[N],in[N],id[N],cnt[N],vis[N],pos[N],dep[N],bel[N],sta[N],ins[N],head[N],f[N][20];
struct path{int a,b;};
struct EDGE{int next,to;}e[N<<1];
IL void make(int a,int b) {e[++tot]=(EDGE){head[a],b},head[a]=tot;}
IL void New_Graph() {
tot=0;
memset(&e,0,sizeof(e));
memset(head,0,sizeof(head));
}
void Dfs(int x) {
RG int i,y;
vis[x]=1,pos[x]=num,S[num].pb(x);
for(i=head[x];i;i=e[i].next)
if(!vis[y=e[i].to]) Dfs(y);
}
void dfs(int x) {
RG int i,y;
for(i=head[x];i;i=e[i].next)
if(!in[y=e[i].to])
bel[y]=bel[x],f[y][0]=x,dep[y]=dep[x]+1,dfs(y);
}
IL void multiply(int Id) {
RG int i,j,x;
for(i=1;i<20;++i)
for(j=0;j<S[Id].size();++j)
x=S[Id][j],f[x][i]=f[f[x][i-1]][i-1];
}
IL path lca(int x,int y) {
RG int i,fl=0,sx=0,sy=0;
if(dep[x]<dep[y]) swap(x,y),fl=1;
for(i=19;i>=0;--i)
if(dep[f[x][i]]>=dep[y]) sx+=1<<i,x=f[x][i];
if(x==y) return fl?(path){sy,sx}:(path){sx,sy};
for(i=19;i>=0;--i)
if(f[x][i]!=f[y][i]) sx+=1<<i,sy+=1<<i,x=f[x][i],y=f[y][i];
return fl?(path){sy+1,sx+1}:(path){sx+1,sy+1};
}
void getcir(int x,int Id) {
if(ins[x]) {
RG int k;
do{k=sta[top--],cir[Id].pb(k),in[k]=1,id[k]=++cnt[Id];}while(k!=x);
return;
}
sta[++top]=x,ins[x]=1,getcir(a[x],Id);
}
IL void getfore(int Id) {
RG int i,x;
for(i=0;i<cnt[Id];++i)
x=cir[Id][i],bel[x]=x,dep[x]=1,dfs(x);
multiply(Id);
}
int main()
{
RG int i,x,y;
n=gi(),m=gi();
for(i=1;i<=n;++i) a[i]=gi(),make(i,a[i]),make(a[i],i);
for(i=1;i<=n;++i)
if(!vis[i]) ++num,Dfs(i);
for(i=1,New_Graph();i<=n;++i) make(a[i],i);
for(i=1;i<=num;++i)
top=0,getcir(S[i][0],i),getfore(i);
while(m--) {
x=gi(),y=gi();
if(pos[x]!=pos[y]) {puts("-1 -1");continue;}
else {
if(bel[x]==bel[y]) {
path s=lca(x,y);
printf("%d %d
",s.a,s.b);
}
else {
int dx=bel[x],dy=bel[y],lx1,lx2,ly1,ly2,Mx1,Mx2,Mi1,Mi2;
ly1=dep[y]-1,lx2=dep[x]-1;
if(id[dx]<id[dy]) lx1=dep[x]-1+cnt[pos[x]]-id[dy]+id[dx],ly2=dep[y]-1+id[dy]-id[dx];
else lx1=dep[x]-1+id[dx]-id[dy],ly2=dep[y]-1+cnt[pos[x]]+id[dy]-id[dx];
Mx1=max(lx1,ly1),Mx2=max(lx2,ly2);
if(Mx1==Mx2) {
Mi1=min(lx1,ly1),Mi2=min(lx2,ly2);
if(Mi1==Mi2) printf("%d %d
",Mx1,Mi1);
else if(Mi1<Mi2) printf("%d %d
",lx1,ly1);
else printf("%d %d
",lx2,ly2);
}
else if(Mx1<Mx2) printf("%d %d
",lx1,ly1);
else printf("%d %d
",lx2,ly2);
}
}
}
return 0;
}