题目

全WA。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
struct node{
	int left,right,sum,lazy;
}tree[N];
struct node1{
	int to,nxt,w;
}edge[N];
int cnt,head[N],dep[N],sz[N],fa[N],son[N],id[N],val[N],topp[N],a[N];
int ans,ans1;
int n,m,r;
int cnm=0;
void pushup(int x){
	tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
}
void build(int x,int l,int r){
	tree[x].left=l;
	tree[x].right=r;
	if(l==r){
		tree[x].sum=val[l];
		return ;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	pushup(x);
}
void pushdown(int x){
	int la=tree[x].lazy;
	if(la!=0){
		tree[x<<1].sum=la;
		tree[x<<1].lazy=la;
		tree[x<<1|1].sum=la;
		tree[x<<1|1].lazy=la;
		tree[x].lazy=0;
	}
}
void update(int x,int l,int r,int p){
	if(l==r){
		tree[x].sum++;
		return ;
	}
	int mid=(l+r)>>1;
	if(p<=mid){
		update(x<<1,l,mid,p);
	}
	else{
		update(x<<1|1,mid+1,r,p);
	}
	pushup(x);
}
int query(int x,int l,int r){
	if(l<=tree[x].left&&r>=tree[x].right){
		return tree[x].sum;
	}
	int mid=(tree[x].left+tree[x].right)>>1;
	int ans=0;
	if(l<=mid){
		ans+=query(x<<1,l,r);
	}
	if(r>mid){
		ans+=query(x<<1|1,l,r);
	}
	return ans;
}
void add(int a,int b,int l){
	edge[++cnt].to=b;
	edge[cnt].w=l;
	edge[cnt].nxt=head[a];
	head[a]=cnt;
}
void dfs1(int u,int f,int dee){
	dep[u]=dee;
	fa[u]=f;
	sz[u]=1;
	int maxx=-1;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==f){
			continue;
		}
		dfs1(v,u,dee+1);
		sz[u]+=sz[v];
		if(sz[v]>maxx){
			son[u]=v;
			maxx=sz[v];
		}
	}
} 
void dfs2(int u,int top){
	id[u]=++cnm;
	val[cnm]=a[u];
	topp[u]=top;
	if(son[u]==0){
		return ;
	}
	dfs2(son[u],top);
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa[u]||v==son[u]){
			continue;
		}
		dfs2(v,v);
	}
}
void query1(int x,int y,int &u,int &v){
	u=v=0;
	int cnttt=0;
	while(topp[x]!=topp[y]){
		if(dep[topp[x]]<dep[topp[y]]){
			swap(x,y);
		}
		v+=query(1,id[topp[x]],id[x]);
		u+=dep[x]-dep[topp[x]]+1; 
		x=fa[topp[x]];
	}
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	v+=query(1,id[y],id[x]);
	u+=dep[x]-dep[y]+1;
}
int vsi[N];
void update1(int x){
	if(vsi[x]==0){
		vsi[x]++;
		update(1,1,n,id[x]);
	}
}
struct cnm3{
	int x,y,c,id,idd;
}ee[N];
int cmp(cnm3 yap,cnm3 yy){
	return yap.c<yy.c;
}
struct cnm1{
	int x,id;
}ee1[N];
struct cnm2{
	int ansa,ansb;
}anss[N];
int cnta,cntb;
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int xx;
		scanf("%lld",&xx);
		if(xx==0){
			r=i;
			continue;
		}
		add(xx,i,1);
		add(i,xx,1);
	}
	dfs1(r,0,1);
	dfs2(r,r);
	build(1,1,n);
	scanf("%lld",&m);
//	for(int i=1;i<=n;i++){
//		cout<<dep[i]<<" ";
//	}
	for(int i=1;i<=m;i++){
		int opt,x,y,z;
		scanf("%lld",&opt);
		if(opt==1){
			cnta++;
			scanf("%lld%lld%lld",&ee[cnta].x,&ee[cnta].y,&x);
			ee[cnta].c=i-x-1;
			ee[cnta].id=cnta;
		} 
		else{
			cntb++;
			scanf("%lld",&ee1[cntb].x);
			ee1[cntb].id=i;
		}
	}
	sort(ee+1,ee+cnta+1,cmp);
	int shu=1;
	for(int i=1;i<=cnta;i++){
		while(shu<=cntb&&ee1[shu].id<=ee[i].c){
			update1(ee1[shu].x);
			shu++;
		}
//		ans=0,ans1=0;
		int u,v;
		query1(ee[shu].x,ee[shu].y,u,v);
		anss[ee[i].id].ansa=u;
		anss[ee[i].id].ansb=v;
//		cout<<ee[i].id<<" "<<endl;
	}
	for(int i=1;i<=cnta;i++){
		printf("%lld %lld\n",anss[i].ansa,anss[i].ansb);
	}
	return 0;
}