记录编号	147211	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	419.[IOI 2009]区域发展	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	36.921 s
提交时间	2015-01-26 21:37:03	内存使用	8.96 MiB

/*====================Asm.Def========================*/
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <iostream>
#include <vector>
using namespace std;
template <typename T>inline void getd(T &x){
	char ch = getchar();bool neg = 0;
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')ch = getchar(), neg = 1;
	x = ch - '0';
	while(isdigit(ch = getchar()))x = x * 10 + ch - '0';
	if(neg)x = -x;
}
/*======================================================*/
typedef long long LL;
const int maxn = 200002, maxr = 25002;
unsigned Sq;

struct SegT;
struct Node{
	int color, L, R;
	vector<Node*> son;
	SegT *ans;
	void dfs();
}node[maxn];
vector<int> Set[maxr], data[maxr];
#define pb push_back

struct SegT{//其实是个可持久化数组......我懒得敲Treap了= =
	int len, mid, val;
	SegT *L, *R;
	SegT(){}
	SegT(int l){
		len = l, mid = len >> 1;
		if(len == 1){val = 0;return;}
		L = new SegT(mid), R = new SegT(len - mid);
	}
	SegT(SegT *t){*this = *t;}
	void Add(int i){
		if(len == 1){++val;return;}
		if(i <= mid){
			L = new SegT(L);
			L->Add(i);
		}
		else{
			R = new SegT(R);
			R->Add(i - mid);
		}
	}
	int Query(int i){
		if(len == 1)return val;
		if(i <= mid)return L->Query(i);
		return R->Query(i - mid);
	}
};

#define GetS(color, i) (\
	upper_bound(data[color].begin(), data[color].end(), i) - 1 - data[color].begin()\
)

void Node::dfs(){
	static int iter = 0;
	L = ++iter;
	data[color].pb(iter);
	ans->Add(color);
	vector<Node*>::iterator it;
	for(it = son.begin();it != son.end();++it){
		(*it)->ans = new SegT(ans);
		(*it)->dfs();
	}
	R = iter;
}

int N, R, Q, Ans[700][700], Ind[700], num[maxr], Acnt = 0;

inline void prework(){
	int i, j, r1, r2;
	vector<int>::iterator it;
	static int Sum[maxn];
	for(j = 1;j <= Acnt;++j){
		r2 = Ind[j];
		memset(Sum, 0, sizeof(int) * (N+1));
		for(it = Set[r2].begin();it != Set[r2].end();++it)++Sum[node[*it].L];
		for(i = 1;i <= N;++i)Sum[i] += Sum[i-1];
		for(i = 1;i <= Acnt;++i){
			if(i == j)continue;
			r1 = Ind[i];
			for(it = Set[r1].begin();it != Set[r1].end();++it)
				Ans[i][j] += Sum[node[*it].R] - Sum[node[*it].L];
		}
	}
}

inline int log2(int x){
	int ans = 1;
	while(x)x >>= 1, ++ans;
	return ans;
}

inline void init(){
	int i, p;
	getd(N), getd(R), getd(Q);
	//Sq = (unsigned)sqrt((double)N);
	//Sq = (unsigned)pow(N, 0.3);
	Sq = (unsigned)(N / sqrt((double)Q * log2(N))) + 1;
	getd(node[1].color);
	Set[node[1].color].pb(1);
	for(i = 2;i <= N;++i){
		getd(p);getd(node[i].color);
		(node + p)->son.pb(node + i);
		Set[node[i].color].pb(i);
	}
	for(i = 1;i <= R;++i){
		data[i].pb(0);
		if(Set[i].size() > Sq){Ind[++Acnt] = i;num[i] = Acnt;}
	}
	node[1].ans = new SegT(R);
	node[1].dfs();
	prework();
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	freopen("output.txt", "w", stdout);
	#else
	freopen("region.in", "r", stdin);
	freopen("region.out", "w", stdout);
	#endif
	
	init();
	int x, y, ans, indx, indy;
	vector<int>::iterator it;
	while(Q--){
		getd(x), getd(y);
		indx = num[x], indy = num[y];
		if(indx && indy){
			printf("%d\n", Ans[indx][indy]);
			fflush(stdout);
			continue;
		}
		ans = 0;
		if(Set[x].size() <= Set[y].size())for(it = Set[x].begin();it != Set[x].end();++it){
			ans -= GetS(y, node[*it].L);
			ans += GetS(y, node[*it].R);
		}
		else for(it = Set[y].begin();it != Set[y].end();++it)
			ans += node[*it].ans->Query(x);
		printf("%d\n", ans);
		fflush(stdout);
	}
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}