此博客停更

以前停了的坑里留下的题，当时太年轻懒得做？

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=2791

我不清楚我写的是不是标算，跑的比别人快$1$倍，难道有特技不成？！

假如，题目中给出的是一棵树，那么就只要算一下$LCA$就可以了，然而题目里给你的是环套外向树森林，蛤，这不是一样的吗，把环上的点拆出来当根，全部变成树然后同一棵树就是$LCA$，不同的树的话环上判一下就好了呀。。多么$naive$

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
#define N 500050
int i,j,k,m,n,x,y,a1,a2,t,len1,len2,fa[N],f[N],LC,vis[N],son[N],cnt,xz[N],id[N],sz[N],top[N],tot,dep[N],bl[N],last[N],sm[N],nm[N];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
struct edge{int to,next;}e[N];bool mrk1[N],mrk2[N];
void dfs1(int x,int d){
	sz[x]=1,dep[x]=d;
	for(int i=last[x],y;i;i=e[i].next)if(!mrk1[y=e[i].to]){
		mrk1[y]=1,xz[y]=xz[x],dfs1(y,d+1),sz[x]+=sz[y];
		if(sz[y]>sz[son[x]])son[x]=y;
	}
}
void dfs2(int x,int d){
	top[x]=d;if(son[x]&&!mrk2[son[x]])mrk2[son[x]]=1,dfs2(son[x],d);
	for(int i=last[x],y;i;i=e[i].next)if(!mrk2[y=e[i].to])mrk2[y]=1,dfs2(y,y);
}
inline void dfs(int x){
	for(int y=x;;x=fa[x]){if(vis[x]==y)break;if(vis[x])return;vis[x]=y;}
	for(;!mrk1[x];x=fa[x])mrk1[x]=mrk2[x]=1;
	for(++tot;!xz[x];x=fa[x])xz[x]=x,nm[x]+=++sm[tot],bl[x]=tot,dfs1(x,1),dfs2(x,x);
}
inline void add(int u,int v){e[++cnt]=(edge){v,last[u]},last[u]=cnt;}
inline int lca(int l,int r){
	for(;top[l]!=top[r];dep[top[l]]<dep[top[r]]?r=fa[top[r]]:l=fa[top[l]]);
	return dep[l]<dep[r]?l:r;
}
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
inline bool check(int a,int b,int c,int d){
	if(max(a,b)<max(c,d))return 1;if(max(a,b)>max(c,d))return 0;
	if(min(a,b)<min(c,d))return 1;if(min(a,b)>min(c,d))return 0;
	return a>=b;
}
int main(){
	for(n=read(),m=read(),i=1;i<=n;++i)f[i]=i;
	for(i=1;i<=n;++i){
		fa[i]=read(),add(fa[i],i);
		int p=find(i),q=find(fa[i]);
		if(p!=q)f[p]=q;
	}
	for(i=1;i<=n;++i)if(!vis[i])dfs(i);
	while(m--){
		int l=read(),r=read();
		if(find(l)!=find(r)){puts("-1 -1");continue;}
		if(xz[l]==xz[r])LC=lca(l,r),printf("%d %d\n",dep[l]-dep[LC],dep[r]-dep[LC]);
		else{
			a1=dep[l]-1,a2=dep[r]-1,t=bl[xz[l]],l=nm[xz[l]],r=nm[xz[r]],len1=(sm[t]+r-l)%sm[t],len2=sm[t]-len1;
			check(a1+len1,a2,a1,a2+len2)?printf("%d %d\n",a1+len1,a2):printf("%d %d\n",a1,a2+len2);
		}
	}
}

$loading...$