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

/*====================Asm.Def========================*/
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <vector>
//#include <iostream>
//#include <map>
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 = 200005, maxr = 25005, maxc = 400;
int N, R, Q;
unsigned Sq;
struct Node{
	int color, L, R;
}node[maxn];
vector<Node*> son[maxn];
#define pb push_back

struct Bracket{
	int loc;
	Node *p;
	Bracket(int l, Node *P):loc(l), p(P){}
	bool operator < (const Bracket &x)const{return loc < x.loc;}
	inline bool isleft(){return loc == p->L;}
};
typedef vector<Bracket> BSeq;
BSeq brack[maxr];//0为所有区域

int itS = 0, Stack[maxn];
bool vis[maxn];
void dfs(){
	static int iter = 0;
	Stack[itS++] = 1;
	while(itS){
		Node *t = node + Stack[itS-1];
		if(vis[Stack[itS-1]]){
			t->R = iter++;
			brack[0].pb(Bracket(t->R, t));
			brack[t->color].pb(Bracket(t->R, t));
			--itS;
			continue;
		}
		vis[Stack[itS-1]] = true;
		t->L = iter++;
		brack[0].pb(Bracket(t->L, t));
		brack[t->color].pb(Bracket(t->L, t));
		for(int it = (int)son[t-node].size()-1;it >= 0;--it)
			Stack[itS++] = son[t-node][it] - node;
	}
}

int Ans1[maxc][maxr], Ans2[maxc][maxr], Ind[maxc], num[maxr], Acnt = 0;

inline void Query(BSeq &O, BSeq &I, int *ans){
	unsigned it1 = 0, it2 = 0;
	if(O.size() >= I.size()){
		int Icnt = (int)I.size() >> 1;
		while(it2 < I.size()){
			while(it1 < O.size() && O[it1] < I[it2]){
				*(ans+O[it1].p->color) += O[it1].isleft() ? Icnt : -Icnt;
				++it1;
			}
			if(I[it2].isleft()) --Icnt;
			++it2;
		}
	}
	else{
		int Ocnt = 0;
		while(it2 < I.size()){
			while(it1 < O.size() && O[it1] < I[it2]){
				if(O[it1].isleft())++Ocnt;
				else --Ocnt;
				++it1;
			}
			if(I[it2].isleft())*(ans+I[it2].p->color) += Ocnt;
			++it2;
		}
	}
}

inline void init(){
	int i, p;
	getd(N), getd(R), getd(Q);
	Sq = (int)(sqrt(N));
	getd(node[1].color);
	for(i = 2;i <= N;++i){
		getd(p);getd(node[i].color);
		son[p].pb(node + i);
	}
	dfs();
	for(i = 1;i <= R;++i)
		if((brack[i].size()>>1) > Sq){Ind[++Acnt] = i;num[i] = Acnt;}
	for(i = 1;i <= Acnt;++i){
		Query(brack[Ind[i]], brack[0], Ans1[i]);
		Query(brack[0], brack[Ind[i]], Ans2[i]);
	}
}

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;
	
	//typedef pair<int, int> Seg;
	//Seg tmp;
	//map<Seg, int> Cache;
	
	while(Q--){
		getd(x), getd(y);
		indx = num[x], indy = num[y];
		if(indx)ans = Ans1[indx][y];
		else if(indy)ans = Ans2[indy][x];
		else{
			/*tmp.first = x, tmp.second = y;
			if(Cache.count(tmp)){
				printf("%d\n", Cache[tmp]);
				fflush(stdout);
				continue;
			}*/
			ans = 0;
			int *t = &ans;
			if(brack[x].size() >= brack[y].size())t -= x;
			else t -= y;
			Query(brack[x], brack[y], t);
			//Cache[tmp] = ans;
		}
		printf("%d\n", ans);
		fflush(stdout);
	}
	
	#if defined DEBUG
	printf("\n%.2lfs\n", (double)clock()/CLOCKS_PER_SEC);
	#endif
	return 0;
}