poi2012 rendezvous

基圈上的外向树求lca。。。先预处理所有的环长，以及外向树内的lca，对每个询问，在一棵树上就直接求，在一个环上就先到根，再判断从哪个方向走，如果不在一个环上输出-1 -1。。。

另：lca不知哪写错了，求大神查错。。。

#include<cstdio>
#include<cmath>
#include<cstring>
int can[500001];
int ansx=0,ansy=0,n,p=0,ss=0,m,sum=0;
int d[500001],pos[500001],fa[500001];
int f[500001][20],root[500001];
int dis[500001],kind[500001],head[500001],next[1000001];
struct re{
	int u,v;
} a[1000001];
inline int max(int a,int b){return a>b? a:b;}
inline int min(int a,int b){return a<b? a:b;}
void getlca(int x,int y){
	ansx=0;  ansy=0;
	if (x==y) return;
	//printf("fu\n");
	if (dis[x]>dis[y]){
		int xx=dis[x]-dis[y];
		ansx=xx;
		int k=int(log2(n));
		while (k>=0){
			if (xx>=(1<<k)){
				x=f[x][k];
				xx-=(1<<k);
			}
			k--;
		}
	}else{
		int xx=dis[y]-dis[x];
		ansy=xx;
		//printf("%d\n",xx);
		int k=int(log2(n));
		while (k>=0){
			if (xx>=(1<<k)){
				y=f[y][k];
				xx-=1<<k;
			}
			k--;
		}
	}
	//printf("f2\n");
	if (x==y) return;
	//printf("ansx=%d ansy=%d\n",ansx,ansy);
	//printf("x\n");
	int k=int(log2(n)); 
	while (k>=0){
		//printf("%d %d %d %d %d\n",k,ansx,ansy,f[x][k],f[y][k]);
		if (f[x][k]!=f[y][k]&&f[x][k]!=0&&f[y][k]!=0){
			ansx+=1<<k;  ansy+=1<<k;
			x=f[x][k];  y=f[y][k];
		}
		k--;
	}
	ansx++;  ansy++;
}
void get(int x,int y){
	if (root[x]==root[y]){
		//printf("e\n");
		getlca(x,y);
		return;
	}
	if (kind[root[x]]!=kind[root[y]]) return;
	ansx=dis[x];  ansy=dis[y];
	x=root[x];  y=root[y];
	int t=kind[x];
	int len=d[t];
	int lx=pos[y]-pos[x];
	if (lx<0) lx+=len;
	int rx=pos[x]-pos[y];
	if (rx<0) rx+=len;
	//printf("len=%d px=%d py=%d\n",len,pos[x],pos[y]);
	//printf("ax=%d ay=%d tx=%d ty=%d\n",ansx,ansy,lx,rx);
	if (max(lx+ansx,ansy)<max(ansx,rx+ansy)){
		//printf("a1\n");
		ansx+=lx;
		return;
	}
	if (max(lx+ansx,ansy)>max(ansx,rx+ansy)){
		//printf("a2\n");
		ansy+=rx;
		return;
	}
	//printf("f1 %d %d\n",ansx,rx+ansy);
	//printf("f2 %d %d\n",ansx+lx,ansy);
	if (min(lx+ansx,ansy)<min(ansx,rx+ansy)){
		//printf("b1\n");
		ansx+=lx;
		return;
	}
	if (min(lx+ansx,ansy)>min(ansx,rx+ansy)){
		//printf("b2\n");
		ansy+=rx;
		return;
	}
	//printf("s\n");
	ansx+=lx;
}
void done(int i){
	root[i]=i;
	kind[i]=++ss;
	d[ss]++;
	pos[i]=++p;
	int j=fa[i];
	while (j!=i){
		//printf("j=%d %d\n",j,i);
		root[j]=j;
		kind[j]=ss;
		d[ss]++;
		pos[j]=++p;
		j=fa[j];
	}
}
void dfs(int i,int x){
	can[i]=x;
	int k=fa[i];
	if (can[k]==x){
		done(k);
		return;
	}
	if (can[k]) return;
	can[k]=x;
	dfs(k,x);
}
void dfs2(int i){
	can[i]=1;
	//printf("ii=%d\n",i);
	int x=int(log2(n));
	f[i][0]=fa[i];
	for (int j=1;j<=x;j++){
		f[i][j]=f[f[i][j-1]][j-1];
	}
	for (int j=head[i];j;j=next[j]){
		int k=a[j].v;
		if (root[k]||can[k]) continue;
		root[k]=root[i];
		dis[k]=dis[i]+1;
		dfs2(k);
	}
}
void build(int u,int v){
	a[++sum].u=u;
	a[sum].v=v;
	next[sum]=head[u];
	head[u]=sum;
}
int main(){
	//freopen("ran3c.in","r",stdin);
	//freopen("ran.out","w",stdout);
	scanf("%d%d",&n,&m);
	int x,y;
	for (int i=1;i<=n;i++){
		scanf("%d",&x);
		build(x,i);  build(i,x);
		fa[i]=x;
	}
	for (int i=1;i<=n;i++){
		if (!can[i]) dfs(i,i);
		//printf("%d\n",can[i]);
	}
	//printf("d\n");
	memset(can,0,sizeof(can));
	for (int i=1;i<=n;i++){
		if (root[i]) dfs2(i);
	}
	//for (int i=1;i<=n;i++) printf("i=%d root=%d dis=%d pos=%d kind=%d\n",i,root[i],dis[i],pos[i],kind[i]);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		ansx=-1;  ansy=-1;
		get(x,y);
		printf("%d %d\n",ansx,ansy);
	}
}