提出 #44157175

---

ソースコード 拡げる

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
namespace fstIO{
	const char _fg='\n';
	int _len=0;
	char ibuf[(1<<20)+1],*iS,*iT,_out[(1<<25)+1],_ar[50];
	#define _gh()\
	(iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),\
	(iS==iT?EOF:*iS++):*iS++)
	#define putc(ch) _out[_len++]=ch
	void read(){}
	template<typename Type,typename...Types>
	void read(Type&x,Types&...xs){
		x=0;
		char ch=_gh();
		char t=0;
		while(ch<'0'||ch>'9')t|=ch=='-',ch=_gh();
		while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=_gh();
		x=t?-x:x;
		read(xs...);
	}
	template<typename Type>
	void write(Type x){
		int tot=0;
		if(!x)putc('0');
		if(x<0)putc('-'),x=-x;
		while(x)_ar[++tot]=x%10+'0',x/=10;
		for(int i=tot;i;--i)putc(_ar[i]);
		putc(_fg);
	}
	void flush(){
		fwrite(_out,1,_len,stdout);
		_len=0;
	}
}
using namespace fstIO;
const int N=200010,M=2*N;
int h[N],e[M],ne[M],idx,l[N],a[N],r[N],dfn,b[N],len,n,m,ans[N],cnt[N],k,res;//don't forget memset h!
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int x,int fa,int d){
	l[x]=++dfn,a[dfn]=d;
	int tot=1;
	Ed{
		int j=e[i];
		if(j==fa)continue;
		tot+=dfs(j, x, d+1);
	}
	r[x]=l[x]+tot-1;
	return tot;
}
struct node{
	int id,l,r,k;
}q[N];
bool cmp(node A,node B){
	int x=b[A.l],y=b[B.l];
	if(x^y)return x<y;
	if(x&1)return A.r<B.r;
	return A.r>B.r;
}
void join(int x){
	++cnt[x];
	res+=x==k;
}
void del(int x){
	--cnt[x];
	res-=x==k;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    read(n);
	memset(h,-1,n*4+4);
	Le(i, 2, n){
		int p;
		read(p);
		add(p,i);
	}
	dfs(1, -1, 0);
	// E(i, n)printf("%d ",a[i]);
	// puts("");
	// return 0;
	read(m);
	len=sqrt((double)n*n/m);
	!len&&(len=1);
	E(i, n)b[i]=i/len;
	E(i, m){
		int a,b;
		read(a,b);
		q[i]={i,l[a],r[a],b};
	}
	sort(q+1,q+1+m,cmp);
	int i=0,j=1;
	E(I, m){
		int l=q[I].l,r=q[I].r,id=q[I].id;k=q[I].k,res=cnt[k];
		Wh(i<r)join(a[++i]);
		Wh(i>r)del(a[i--]);
		Wh(j<l)del(a[j++]);
		Wh(j>l)join(a[--j]);
		ans[id]=res;
	}
	E(i, m)write(ans[i]);
	flush();
    return 0;
}

提出情報

ジャッジ結果