rt,手算内存不超过$40MB$,但是MLE了。

提交记录

#include<bits/stdc++.h>
using namespace std;
int n,m,q,flag[100009],d[100009],dfn[100009],tot,h[100009],ver[100009],nxt[100009],st[100009][19],ts[100009][19],sz[100009],lg,v[800009],ls[800009],rs[800009],rot[100009],a[500009],b[500009],c[500009],id[500009],ans[100009],anss[100009];
void dfs(int x,int fa){
	dfn[x]=++tot;
	d[x]=d[fa]+1;
	sz[x]=1;
	for(int i=h[x];i;i=nxt[i]){
		dfs(ver[i],x);
		sz[x]+=sz[ver[i]];
	} 
	return;
}
void dfs2(int x){
	for(int i=h[x];i;i=nxt[i]){
		dfs2(ver[i]);
		if(d[ts[x][0]]>d[ts[ver[i]][0]])ts[x][0]=ts[ver[i]][0];
	} 
	return;
}
int lca(int x,int y){
	if(d[x]<d[y])swap(x,y);
	if(dfn[x]>=dfn[y]&&dfn[x]<dfn[y]+sz[y])return y;
	for(int i=lg;i>=0;i--){
		int t=st[y][i];
		if(dfn[x]<dfn[t]||dfn[x]>=dfn[t]+sz[t])y=t;
	}
	if(dfn[x]>=dfn[y]&&dfn[x]<dfn[y]+sz[y])return y;
	else return st[y][0];
}
bool cmp(const int &x,const int &y){
	if(a[x]!=a[y])return a[x]<a[y];
	if(b[x]!=b[y])return b[x]<b[y];
	return x<y;
}
int main(){
	scanf("%d",&n);
	for(int i=2,fa;i<=n;i++){
		scanf("%d",&fa);
		st[i][0]=fa;
		tot++;
		nxt[tot]=h[fa];
		h[fa]=tot;
		ver[tot]=i;
	}
	lg=log2(n)+1;
	for(int i=1;i<=lg;i++){
		for(int j=1;j<=n;j++){
			st[j][i]=st[st[j][i-1]][i-1];
		}
	}
	tot=0;
	dfs(1,0);
	sz[0]=n+1;
	d[0]=n+1;
	dfn[0]=0;
	scanf("%d",&m);
	tot=0;
	for(int i=1,x,y,z;i<=m;i++){
		scanf("%d%d",&x,&y);
		if(dfn[x]>dfn[y])swap(x,y);
		a[i]=dfn[x]+1;
		b[i]=dfn[y]+1;
		id[i]=i;
		z=lca(x,y);
		if(d[ts[x][0]]>d[z])ts[x][0]=z;
		if(d[ts[y][0]]>d[z])ts[y][0]=z;
	}
	tot=m;
	dfs2(1);
	for(int i=1;i<=lg;i++){
		for(int j=1;j<=n;j++){
			ts[j][i]=ts[ts[j][i-1]][i-1];
		}
	}
	scanf("%d",&q);
	d[0]=-1;
	int nw=tot; 
	for(int i=1,x,y,z;i<=q;i++){
		scanf("%d%d",&x,&y);
		z=lca(x,y);
		ans[i]=0;
		for(int j=lg;j>=0;j--){
			if(d[ts[x][j]]>d[z]){
				x=ts[x][j];
				ans[i]+=1<<j;
			}
		}
		for(int j=lg;j>=0;j--){
			if(d[ts[y][j]]>d[z]){
				y=ts[y][j];
				ans[i]+=1<<j;
			}
		}
		if(d[ts[x][0]]>d[z]||d[ts[y][0]]>d[z]||(ts[x][0]==0&&x!=z)||(ts[y][0]==0&&y!=z))ans[i]=-1;
		if(dfn[x]>dfn[y])swap(x,y);
		if(dfn[y]>=dfn[x]&&dfn[y]<dfn[x]+sz[x])flag[i]=1;
		a[++tot]=dfn[x];
		b[tot]=dfn[y];
		id[tot]=tot;
		a[++tot]=dfn[x];
		b[tot]=dfn[y]+sz[y];
		id[tot]=tot;
		a[++tot]=dfn[x]+sz[x];
		b[tot]=dfn[y];
		id[tot]=tot;
		a[++tot]=dfn[x]+sz[x];
		b[tot]=dfn[y]+sz[y];
		id[tot]=tot;
		anss[i]=tot;
	}
	sort(id+1,id+tot+1,cmp);
	int wn=1;
	for(int i=1;i<=tot;i++){
		if(id[wn]<=nw){
			for(int j=b[id[wn]];j<=n+5;j+=(j&(-j)))v[j]++;
		}
		else{
			c[id[wn]]=0;
			for(int j=b[id[wn]];j;j-=(j&(-j)))c[id[wn]]+=v[j];
		}
		wn++;
	}
	for(int i=1;i<=q;i++){
		if(ans[i]==-1)puts("-1");
		else if(c[anss[i]]-c[anss[i]-1]-c[anss[i]-2]+c[anss[i]-3]>0||flag[i])printf("%d\n",ans[i]+1);
		else printf("%d\n",ans[i]+2);
	}
	return 0;
}