题目：UVA1327 acwing上的单数据过了（可能还有多测的问题）

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e5;
struct rec{
	int e,nex;
}z[2*N],g[2*N];
int en=1,fi[N];
void add(int s,int e){
	z[++en].e=e;
	z[en].nex=fi[s];
	fi[s]=en;
}
int ne=1,hea[N];
void add1(int s,int e){
	g[++ne].e=e;
	g[ne].nex=hea[s];
	hea[s]=ne;
}
int n,tt;
int in[N];
void init(){
	scanf("%d%d",&n,&tt);
	for (int i=1;i<=n;++i){
		int v;
		scanf("%d",&v);
		add(v,i);
		add(i,v);
		add1(i,v);in[v]++;
	}
}
bool vis[2*N],vis1[N];
int f[N],deep[N],tot,p[N];
void dfs1(int u,int fa){
	p[u]=tot;
	deep[u]=deep[fa]+1;f[u]=fa;
	for (int i=fi[u];i!=0;i=z[i].nex){
		if (vis[i]||deep[z[i].e]!=0) continue;
		vis[i]=vis[i^1]=true;
		dfs1(z[i].e,u);
	}
}
int val[N],v[N];
void q_huan(int rt1,int rt2,int w){
	if (deep[rt1]<deep[rt2]) swap(rt1,rt2);
	v[w]=deep[rt1]-deep[rt2]+1;
	if (rt1==rt2) v[w]=0;
	while (rt1!=rt2){
		vis1[rt1]=true;
		rt1=f[rt1];
	}
	vis1[rt2]=true;
}
bool vis2[N],vis3[N];
void dfs4(int u){
	vis2[u]=true;
	for (int i=hea[u];i!=0;i=g[i].nex){
		if (vis2[g[i].e]) continue;
		val[g[i].e]=val[u]+1;
		dfs4(g[i].e);
	}
}
int rt1,rt2;
void ycl(){
	for (int i=1;i<=n;++i){
		for (int j=fi[i];j!=0;j=z[j].nex){
			if (vis[j]==false){
				rt1=i,rt2=z[j].e;
				vis[j]=vis[j^1]=true;
				q_huan(rt1,rt2,p[rt1]);
			}
		}
	}
}
int top[N],siz[N],son[N],root[N];
void dfs2(int u,int fa,int ye){
	root[u]=ye;
	f[u]=fa;deep[u]=deep[fa]+1;siz[u]=1;son[u]=-1;
	for (int i=fi[u];i!=0;i=z[i].nex){
		if (z[i].e==fa||vis1[z[i].e]) continue;
		dfs2(z[i].e,u,ye);
		siz[u]+=siz[z[i].e];
		if (son[u]==-1||siz[son[u]]<siz[z[i].e]) son[u]=z[i].e;
	}
}
void dfs3(int u,int topp){
	top[u]=topp;
	if (son[u]==-1) return ;
	dfs3(son[u],topp);
	for (int i=fi[u];i!=0;i=z[i].nex){
		if (z[i].e==f[u]||z[i].e==son[u]||vis1[z[i].e]) continue;
		dfs3(z[i].e,z[i].e);
	}
}
int q_lca(int x,int y){
	while (top[x]!=top[y]){
		if (deep[top[x]]<deep[top[y]]){
			swap(x,y);
		}
		x=f[top[x]];
	}
	return deep[x]<deep[y]?x:y;
}
void work(){
	for (int i=1;i<=n;++i){
		if (deep[i]==0){
			++tot;
			dfs1(i,0); 
		}
	}
	ycl();
	for (int i=1;i<=n;++i){
		deep[i]=0;f[i]=0;
	}
	for (int i=1;i<=n;++i){
		if (vis1[i]==true){
			dfs2(i,0,i);
			dfs3(i,i);
		}
	}
	for (int i=1;i<=n;++i){
		if (vis3[p[i]]==false&&in[i]==0){
			vis3[p[i]]=true;
			dfs4(i);
		}
	}
	for (int i=1;i<=n;++i){
		if (vis3[p[i]]==false){
			vis3[p[i]]=true;
			dfs4(i);
		}
	}
	for (int i=1;i<=tt;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		if (p[x]!=p[y]){
			printf("-1 -1\n");
		}
		else{
			if (root[x]==root[y]){
				int lca=q_lca(x,y);
				printf("%d %d\n",deep[x]-deep[lca],deep[y]-deep[lca]);
			}
			else{
				int sum1=deep[x]-deep[root[x]],sum2=deep[y]-deep[root[y]],ans1,ans2,ans3,ans4;
			//	printf("sum1=%d sum2=%d val1=%d val2=%d val3=%d\n",sum1,sum2,val[root[x]],val[root[y]],v[p[x]]);
				if (val[root[x]]<val[root[y]]){
					ans1=val[root[y]]-val[root[x]]+sum1,ans2=sum2;
					ans3=sum1,ans4=v[p[x]]-(val[root[y]]-val[root[x]])+sum2;
				}
				else{
					ans1=v[p[x]]-(val[root[x]]-val[root[y]])+sum1,ans2=sum2;
					ans3=sum1,ans4=val[root[x]]-val[root[y]]+sum2;
				}
			//	printf("ans1=%d ans2=%d ans3=%d ans4=%d\n",ans1,ans2,ans3,ans4);
				if (max(ans1,ans2)<max(ans3,ans4)) printf("%d %d\n",ans1,ans2);
				else if (max(ans1,ans2)>max(ans3,ans4)) printf("%d %d\n",ans3,ans4);
				else{
					if (min(ans1,ans2)<min(ans3,ans4)) printf("%d %d\n",ans1,ans2);
					else if (min(ans1,ans2)>min(ans3,ans4)) printf("%d %d\n",ans3,ans4);
					else{
						if (ans1>ans3) printf("%d %d\n",ans1,ans2);
						else printf("%d %d\n",ans3,ans4);
					}
				}
			}
		}
	}
/*	for (int i=1;i<=n;++i){
		printf("u=%d fa=%d deep=%d top=%d p=%d\n",i,f[i],deep[i],top[i],p[i]);
		if (vis1[i]==true) printf("u=%d val=%d\n",i,val[i]);	
	}
	for (int i=1;i<=tot;++i){
		printf("i=%d v=%d\n",i,v[i]);
	}
*/
}
int main(){
	init();
	work();
	return 0;
}