求助...
查看原帖
求助...
436389
Vidoliga楼主2022/5/14 11:26

怎么调样例都过不了。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 700010
#define LGN 22
#define Inf 0x3f3f3f3f
using namespace std;
inline int read(){
	register int d=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){d=(d<<1)+(d<<3)+(ch^48);ch=getchar();}
	return d*f;
}
void writes(int x){
	if(x>9) writes(x/10);
	putchar(x%10+48);
}
inline void write(int x){
	if(x<0) putchar('-'),writes(-x);
	else writes(x);
	putchar('\n');
}
int n,m,q,pcnt;
struct Node{
	int x,y,id;
}p[N<<2],d[N<<2];
int s[N<<2];
int res[N<<2],ans[N<<2];
void cdq(int l,int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	cdq(l,mid);cdq(mid+1,r);
	int i=l,j=mid+1,pos=l,tot=0;
	while(i<=mid||j<=r){
		if(j>r||(i<=mid&&p[i].y<=p[j].y)){
			if(p[i].id>2*m) tot++;
			d[pos++]=p[i++];
		}
		else {ans[p[j].id]+=i-l-tot;d[pos++]=p[j++];}
	}
	for(int i=l;i<=r;i++) p[i]=d[i];
}
inline bool cmp(Node a,Node b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}
struct Edge{
	int v,nxt;
}edge[N<<1];
int head[N],cnt;
inline void add(int u,int v){
	edge[++cnt].v=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
int dfn[N],dep[N],fa[N][LGN],lg[N],ncnt;
void init(int n){ 
	lg[0]=0;
	for(int i=1;i<=n;i++){
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	} 
	return;
}
void dfs1(int u,int F){
	dfn[u]=++ncnt;
	fa[u][0]=F;dep[u]=dep[F]+1; 
	for(int i=1;i<=lg[dep[u]];i++){ 
		fa[u][i]=fa[fa[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=edge[i].nxt){
		if(edge[i].v==F) continue;
		dfs1(edge[i].v,u);
	}
	s[u]=ncnt;
	return; 
}
int LCA(int x,int y){ 
	if(dep[x]<dep[y]) swap(x,y); 
	while(dep[x]>dep[y]){
		x=fa[x][lg[dep[x]-dep[y]]-1];
	}
	if(x==y) return x;
	for(int k=lg[dep[x]]-1;k>=0;k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k],y=fa[y][k];
		} 
	}
	return fa[x][0];
}
int f[N][LGN];
void dfs2(int u){
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].v;
		if(v==fa[u][0]) continue;
		dfs2(v);
		if(dep[f[v][0]]<dep[u]){
			if(dep[f[v][0]]<dep[f[u][0]]) f[u][0]=f[v][0];
		}
	}
}
int Ans[N];
bool Flag[N];
signed main(){
	n=read();init(N-5);
	for(int i=2;i<=n;i++){
		int p=read();
		add(i,p),add(p,i);
	}
	dfs1(1,0);dep[0]=Inf;
	m=read();
	for(int i=1;i<=m;i++){
		int a=read(),b=read();
		int lca=LCA(a,b);
		p[(i-1)<<1].x=dfn[a],p[(i-1)<<1].y=dfn[b],p[(i-1)<<1].id=(i-1)<<1;
		p[(i-1)<<1|1].x=dfn[b],p[(i-1)<<1|1].y=dfn[a],p[(i-1)<<1|1].id=((i-1)<<1|1);
		if(dep[f[a][0]]>dep[lca]) f[a][0]=lca;
		if(dep[f[b][0]]>dep[lca]) f[b][0]=lca;
	}
	pcnt=2*m;
	dfs2(1);
	for(int i=1;i<=n;i++) if(f[i][0]==i) f[i][0]=0;
	for(int j=1;j<=18;j++)
		for(int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	q=read();
	for(int k=1;k<=q;k++){
		int a=read(),b=read();
		int lca=LCA(a,b);
		for(int j=18;j>=0;j--){
			if(dep[lca]<=dep[f[a][j]]&&f[a][j]!=0&&f[a][j]!=lca) a=f[a][j],Ans[k]+=(1<<j);
		}
		for(int j=18;j>=0;j--){
			if(dep[lca]<=dep[f[b][j]]&&f[b][j]!=0&&f[b][j]!=lca) b=f[b][j],Ans[k]+=(1<<j);
		}
		if(a==lca||b==lca){
			if(b==lca) swap(a,b);
			if(dep[lca]>=dep[f[b][0]]) Ans[k]++;
			else Ans[k]=-1;
		}
		else{
			bool x=(dep[lca]<=dep[f[a][0]])&&f[a][0]!=0&&f[a][0]!=lca,y=(dep[lca]<=dep[f[b][0]])&&f[b][0]!=0&&f[b][0]!=lca;
			if(x&&y) Ans[k]=-1;
			else if((!f[a][0])||(!f[b][0])) Ans[k]=-1;
			else{
				Flag[k]=true;
				Ans[k]+=2;
			}
		}
		p[++pcnt].x=dfn[a]-1,p[pcnt].y=dfn[b]-1,p[pcnt].id=pcnt;
		p[++pcnt].x=s[a],p[pcnt].y=dfn[b]-1,p[pcnt].id=pcnt;
		p[++pcnt].x=dfn[a]-1,p[pcnt].y=s[b],p[pcnt].id=pcnt;
		p[++pcnt].x=s[a],p[pcnt].y=s[b],p[pcnt].id=pcnt;
	}
	sort(p+1,p+pcnt+1,cmp);
	cdq(1,pcnt);
	int j=1;
	for(int i=2*m+1;i<=pcnt;i+=4,j++){
		res[j]=ans[i]-ans[i+1]-ans[i+2]+ans[i+3];
	}
	for(int i=1;i<=j;i++){
		if(!Flag[i]) continue;
		if(Ans[i]==-1) continue;
		if(res[i]) Ans[i]--;
	}
	for(int i=1;i<=q;i++) printf("%d\n",Ans[i]);
	return 0;
}
2022/5/14 11:26
加载中...