记录编号	155901	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAATAA
题目名称	[IOI 2009]区域发展	最终得分	96
用户昵称	TA	是否通过	未通过
代码语言	C++	运行时间	35.080 s
提交时间	2015-03-31 20:32:40	内存使用	14.91 MiB

#include<cstdio> 
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
inline int in(){
	char c=getchar();
	int x=0;
	while(c<'0'||c>'9')c=getchar();
	for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
	return x;
}
int H[200005];
#include<vector>
vector<int> son[200005];
struct QS{
	int r1,r2,i;
	long long ans;
	inline bool operator < (const QS a) const{
		return r1!=a.r1?r1<a.r1:r2<a.r2;
	}
	inline bool operator != (const QS a) const{
		return r1!=a.r1||r2!=a.r2;
	}
	inline bool operator == (const QS a) const{
		return r1==a.r1&&r2==a.r2;
	}
}query[200005];;
vector<int> qc[25005],qi[25005];
long long ans[200005];
int sum[25005];
int pc[200005],pi[200005],qs[25005],qt[25005];
int ps[200005],ss[200005],st[200005];
#include<cstdlib>
int soni[200005],fa[200005];
int main(){
	freopen("region.in","r",stdin);
	freopen("region.out","w",stdout);
	int N=in(),R=in(),Q=in(),i,j;
	H[1]=in();
	for(i=2;i<=N;++i)fa[i]=in(),son[fa[i]].push_back(i),H[i]=in();
	for(i=0;i<Q;++i)query[i].r1=in(),query[i].r2=in(),query[i].i=i;
	sort(query,query+Q);
	for(i=0;i<Q;++i)
		if(query[i]!=query[i+1])
			qc[query[i].r2].push_back(query[i].r1),qi[query[i].r2].push_back(i);
	int tot=0;
	for(i=1;i<=R;++i){
		qs[i]=tot;
		qt[i]=tot+qc[i].size();
		for(j=qc[i].size();j--;)pc[tot]=qc[i][j],pi[tot++]=qi[i][j];
	}
	tot=0;
	for(i=1;i<=N;++i){
		ss[i]=tot,st[i]=tot+son[i].size();
		for(j=son[i].size();j--;)ps[tot++]=son[i][j];
	}
	
	memset(soni,-1,sizeof(soni));
	for(int x=1;x;)
		if(soni[x]<0){
			for(i=qs[H[x]];i<qt[H[x]];++i)query[pi[i]].ans+=sum[pc[i]];
			++sum[H[x]];
			soni[x]=st[x];
		}
		else if(soni[x]>ss[x])x=ps[--soni[x]];
		else{
			--sum[H[x]];
			x=fa[x];
		}
	
	for(i=Q;i--;){
		if(query[i]==query[i+1])query[i].ans=query[i+1].ans;
		ans[query[i].i]=query[i].ans;
	}
	for(i=0;i<Q;++i)printf("%lld\n",ans[i]);
}