【分析】
一开始以为是无向边ORZ。。
其实有向边只要改一点点东西。
那个x>=y是用来省掉SPJ的，不是题目要求
无向边的话，首先是一个基环森林，很明显是求最短路径然后除以二。
有向边的话，很多路径是固定的，
首先不是一个联通块的一定无法到达，是一个联通块的一定能到达（也许你觉得有向边不一定可以，但事实上是可以的，因为每个点只有一条出边的特殊性质）
这种特殊性质告诉我们：
环一定是通的，就是从环上任意一点走环一定能走回自己。
基环树下面的点的连边一定是向上的（考虑一个点只有一条出边，而环上的根的出边已经贡献给环了）
所以如果是同一棵树，那么求LCA，答案是唯一的。
如果不是，那么环上面也只有两种走法，两个答案比较一下即可。
【其实一开始看错题之后觉得边有向很难搞，其实知道性质就很简单了】
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 500010 int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
int myabs(int x) {return x>?x:-x;} struct node
{
int x,y,next,o;
bool p;
}t[Maxn*];int len=;
int first[Maxn]; void ins(int x,int y)
{
t[++len].x=x;t[len].y=y;
t[len].next=first[x];first[x]=len;
t[len].p=;
if(len%==) t[len].o=len-;
else t[len].o=len+;
} int fa[Maxn],r1[Maxn],r2[Maxn];
int ffa(int x)
{
if(x!=fa[x]) fa[x]=ffa(fa[x]);
return fa[x];
} int dis[Maxn];
bool onc[Maxn];
int dfs0(int x,int ff,int rr)
{
dis[x]=dis[ff]+;
if(x==rr) {onc[x]=;return ;}
for(int i=first[x];i;i=t[i].next) if(t[i].y!=ff)
{
int y=t[i].y,z=dfs0(y,x,rr);
if(z!=) {t[i].p=t[t[i].o].p=;onc[x]=;return z+;}
}
return ;
} int tp[Maxn],son[Maxn],sm[Maxn];
int dep[Maxn],siz[Maxn],fd[Maxn];
void dfs1(int x,int ff)
{
sm[x]=;son[x]=;fd[x]=ff;
for(int i=first[x];i;i=t[i].next) if(t[i].p&&t[i].y!=ff)
{
int y=t[i].y;
dis[y]=dis[x];
dep[y]=dep[x]+;
dfs1(y,x);
sm[x]+=sm[y];
if(son[x]==||sm[son[x]]<sm[y]) son[x]=y;
}
} void dfs2(int x,int ff,int tpp)
{
tp[x]=tpp;
if(son[x]) dfs2(son[x],x,tpp);
for(int i=first[x];i;i=t[i].next) if(t[i].y!=ff&&t[i].y!=son[x]&&t[i].p)
{
dfs2(t[i].y,x,t[i].y);
}
} void ffind(int x,int y)
{
int xx=x,yy=y;
while(tp[x]!=tp[y])
{
if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
x=fd[tp[x]];
}
if(dep[x]>dep[y]) swap(x,y);
// return dep[xx]+dep[yy]-2*dep[x];
printf("%d %d\n",dep[xx]-dep[x],dep[yy]-dep[x]);
} int main()
{
int n,q;
scanf("%d%d",&n,&q);
memset(first,,sizeof(first));
memset(r1,,sizeof(r1));
memset(onc,,sizeof(onc));
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
if(ffa(x)==ffa(i))
{
r1[ffa(x)]=x;r2[ffa(x)]=i;
}
else
{
if(r1[ffa(x)]!=) r1[ffa(i)]=r1[ffa(x)],r2[ffa(i)]=r2[ffa(x)];
fa[ffa(x)]=ffa(i);
ins(x,i);ins(i,x);
}
}
for(int i=;i<=n;i++) if(ffa(i)==i)
{
dis[r1[i]]=;
siz[i]=dfs0(r1[i],,r2[i]);
}
for(int i=;i<=n;i++) if(onc[i])
{
dep[i]=;
dfs1(i,);
dfs2(i,,i);
}
for(int i=;i<=q;i++)
{
int x,y;
scanf("%d%d",&x,&y);
if(ffa(x)!=ffa(y)) {printf("-1 -1\n");continue;}
int sum;
if(dis[x]!=dis[y])
{
sum=mymin(siz[ffa(x)]-myabs(dis[x]-dis[y]),myabs(dis[x]-dis[y]));
int x1,y1,x2,y2;
if(dis[x]<dis[y])
{
x1=dep[x]+dis[y]-dis[x];y1=dep[y];
x2=dep[x];y2=dep[y]+siz[ffa(x)]-(dis[y]-dis[x]);
}
else
{
x1=dep[x];y1=dep[y]+dis[x]-dis[y];
x2=dep[x]+siz[ffa(x)]-(dis[x]-dis[y]);y2=dep[y];
}
if(mymax(x1,y1)<mymax(x2,y2)) printf("%d %d\n",x1,y1);
else if(mymax(x1,y1)>mymax(x2,y2)) printf("%d %d\n",x2,y2);
else
{
if(mymin(x1,y1)<mymin(x2,y2)) printf("%d %d\n",x1,y1);
else if(mymin(x1,y1)>mymin(x2,y2)) printf("%d %d\n",x2,y2);
else if(x1>=y1) printf("%d %d\n",x1,y1);
else printf("%d %d\n",x2,y2);
}
}
else ffind(x,y);
}
return ;
}
2017-02-15 22:07:35