记录编号	140780	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[IOI 2009]区域发展	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	11.614 s
提交时间	2014-11-25 08:49:43	内存使用	103.35 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int SIZEN=200010,SIZER=25010,SIZEB=500;
int N,R,Q,B;
vector<int> c[SIZEN];
int H[SIZEN]={0};
int rsz[SIZEN]={0};
int S[SIZEN]={0};
int pans1[SIZEB][SIZER]={0},pans2[SIZEB][SIZER]={0};
vector<int> reg[SIZER];
vector<pair<int,int> > endpoint[SIZER];
int subsz[SIZEN]={0},tim[SIZEN]={0};
vector<int> dfslis;
int ttot=0;
void DFS(int x){
	tim[x]=++ttot;
	subsz[x]=1;
	dfslis.push_back(x);
	for(int i=0;i<c[x].size();i++){
		DFS(c[x][i]);
		subsz[x]+=subsz[c[x][i]];
	}
}
void calc_1(vector<pair<int,int> > &ep,vector<int> &t,int ans[SIZER]){
	//区域R1的端点信息在ep,对于t中的每个人计算他对自己地区答案的贡献(作为e2),计入ans
	//ep[i].first是时间,ep[i].second是事件,而t中存的是人
	//要求t已按照DFS编号顺序排序
	int now=0,p1=0,p2=0;
	while(p2<t.size()){
		if(p1<ep.size()&&ep[p1].first<=tim[t[p2]]) now+=ep[p1++].second;//端点优先结算
		else ans[H[t[p2++]]]+=now;
	}
}
int ans[SIZER]={0};
int calc_1(int r1,int r2){
	calc_1(endpoint[r1],reg[r2],ans);
	int k=ans[r2];ans[r2]=0;
	return k;
}
int presum[SIZEN]={0};
void calc_2(vector<int> &t,int ans[SIZER]){//区域r2的所有人是t,计算每个r1的答案
	//要求t已按DFS编号顺序排序
	memset(presum,0,sizeof(presum));
	for(int i=0;i<t.size();i++) presum[tim[t[i]]]=1;
	for(int i=1;i<=N;i++) presum[i]+=presum[i-1];
	for(int i=1;i<=N;i++) ans[H[i]]+=presum[tim[i]+subsz[i]-1]-presum[tim[i]-1];
}
int id[SIZER]={0};
void prepare(void){
	for(int i=0;i<N;i++){
		int x=dfslis[i];
		reg[H[x]].push_back(x);
		endpoint[H[x]].push_back(make_pair(tim[x],1));
		endpoint[H[x]].push_back(make_pair(tim[x]+subsz[x],-1));
	}
	for(int i=1;i<=R;i++) sort(endpoint[i].begin(),endpoint[i].end());
	int tot=0;
	for(int i=1;i<=R;i++){
		if(rsz[i]>=B){
			id[i]=++tot;
			calc_1(endpoint[i],dfslis,pans1[tot]);
			calc_2(reg[i],pans2[tot]);
		}
	}
}
void work(void){
	int r1,r2;
	for(int i=1;i<=Q;i++){
		scanf("%d%d",&r1,&r2);
		if(id[r1]) printf("%d\n",pans1[id[r1]][r2]);
		else if(id[r2]) printf("%d\n",pans2[id[r2]][r1]);
		else printf("%d\n",calc_1(r1,r2));
	}
}
void read(void){
	scanf("%d%d%d",&N,&R,&Q);
	B=sqrt(N+0.0);
	for(int i=1;i<=N;i++){
		if(i>1){
			scanf("%d",&S[i]);
			c[S[i]].push_back(i);
		}
		scanf("%d",&H[i]);
		rsz[H[i]]++;
	}
}
int main(){
	freopen("region.in","r",stdin);
	freopen("region.out","w",stdout);
	read();
	DFS(1);
	prepare();
	work();
	return 0;
}