记录编号	155820	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	419.[IOI 2009]区域发展	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	25.199 s
提交时间	2015-03-30 21:48:53	内存使用	7.94 MiB

#include<cstdio> 
#include<cstring>
#include<iostream>
#include<ctime>
#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;
	int 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];
int ans[200005];
int sum[25005],num[25005];
#include<cstdlib>
inline void dfs(int x){
	for(int i=num[H[x]];i--;)query[qi[H[x]][i]].ans+=sum[qc[H[x]][i]];
	++sum[H[x]];
	for(int i=son[x].size();i--;)dfs(son[x][i]);
	--sum[H[x]];
}
int main(){
	freopen("region.in","r",stdin);
	freopen("region.out","w",stdout);
	int N=in(),R=in(),Q=in(),i;
	H[1]=in();
	for(i=2;i<=N;++i)son[in()].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);
	for(i=1;i<=R;++i)num[i]=qi[i].size();
	dfs(1);
	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("%d\n",ans[i]);
}