ioi的数据结构题，果然还是比较BT的。

做法是对颜色分开，大的颜色预处理，小的颜色直接暴力。

然后一个小错又坑了好久。我真的没救了。

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <algorithm>

using namespace std;

const int buf_len = 4000;
const size_t buf_size = buf_len * sizeof(char);
char buf[buf_len], *bufb(buf), *bufe(buf + 1);
#define readBuf() { \
	if (++ bufb == bufe) \
		bufe = (bufb = buf) + fread(buf, 1, buf_size, stdin); \
}
#define readInt(_x_) { \
	register int _s_(0); \
	do { \
		readBuf(); \
	} while (!isdigit(*bufb)); \
	do { \
		_s_ = _s_ * 10 + *bufb - 48; \
		readBuf(); \
	} while (isdigit(*bufb)); \
	_x_ = _s_; \
}

struct edge {
	int t;
	edge *next;
};
typedef pair <int, int> ninfo;
typedef long long dint;

#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif

const int maxn = 200009;
const int maxb = 259;
const int maxbn = 800;
const int maxc = 25009;

int n, r, q, c[maxn], bi[maxc], bc[maxn], nod[maxn];
int dfb[maxn], dfe[maxn], dfo[maxn];
dint bn[maxb][maxc], nb[maxb][maxc];
edge *head[maxn], elst[maxn], *ep(elst);
ninfo ni[maxn], ci[maxn];

struct bin_tree {
	int a[maxn], t[maxn], c;
	bin_tree() {
		c = 0;
		memset(t, 0, sizeof(t));
	}
	void chg(int p, int v) {
		for (; p <= n; p += (p & -p))
			if (t[p] < c)
				t[p] = c, a[p] = v;
			else
				a[p] += v;
	}
	int qry(int p) {
		int s(0);
		for (; p; p -= (p & -p))
			if (t[p] == c)
				s += a[p];
		return s;
	}
};

bin_tree bt;

inline void addEdge(int u, int v) {
	ep-> t = v;
	ep-> next = head[u];
	head[u] = ep ++;
}

void buildTree() {
	static int stc[maxn];
	int tst(1), dfn(0);
	stc[1] = 1;
	while (tst) {
		int p(stc[tst --]);
		dfo[dfb[p] = dfe[p] = ++ dfn] = p;
		for (edge* e = head[p]; e; e = e-> next)
			stc[++ tst] = e-> t;
	}
	for (int ti = n; ti; -- ti) {
		int p(dfo[ti]);
		for (edge* e = head[p]; e; e = e-> next)
			if (dfe[e-> t] > dfe[p])
				dfe[p] = dfe[e-> t];
	}
}

void preAns() {	
	static int ca[maxn], cb[maxn];
	memset(bn, 0, sizeof(bn));
	memset(nb, 0, sizeof(nb));
	for (int i = 1; i <= n; ++ i)
		ni[i - 1] = ninfo(c[i], i);
	sort(ni, ni + n);
	memset(cb, 0, sizeof(cb));
	memset(bi, -1, sizeof(bi));
	int tb(0);
	for (int i = 0, j; i < n; i = j) {
		for (j = i; j < n && ni[j]. first == ni[i]. first; ++ j)
			nod[j] = ni[j]. second;
		bc[ni[i]. first] = i;
		ci[tb ++] = ninfo(i - j, ni[i] .first);
	}
	sort(ci, ci + tb);
	for (int ti = 0; ti < tb && ti < maxb; ++ ti) {
		int i(bc[ci[ti]. second]), j(i - ci[ti]. first);
		bi[ni[i]. first] = ti;
		memset(ca, 0, sizeof(ca));
		memset(cb, 0, sizeof(cb));
		for (int k = i; k < j; ++ k) {
			++ ca[dfb[nod[k]]];
			++ cb[dfb[nod[k]]];
			-- cb[dfe[nod[k]] + 1];
		}
		for (int k = 1; k <= n; ++ k)
			ca[k] += ca[k - 1], cb[k] += cb[k - 1];
		for (int p = 1; p <= n; ++ p) {
			nb[ti][c[p]] += ca[dfe[p]] - ca[dfb[p] - 1];
			bn[ti][c[p]] += cb[dfb[p]];
		}
	}
}

dint query(int r1, int r2) {
	dint ans(0);
	++ bt. c;
	for (int i = bc[r2]; i < n && c[nod[i]] == r2; ++ i)
		bt. chg(dfb[nod[i]], 1);
	for (int i = bc[r1]; i < n && c[nod[i]] == r1; ++ i)
		ans += bt. qry(dfe[nod[i]]) - bt. qry(dfb[nod[i]] - 1);
	return ans;
}

int main() {
#ifndef ONLINE_JUDGE
	//freopen("in.txt", "r", stdin);
#endif

	readInt(n);
	readInt(r);
	readInt(q);
	readInt(c[1]);
	memset(head, 0, sizeof(head));
	for (int i = 2; i <= n; ++ i) {
		int u;
		readInt(u);
		readInt(c[i]);
		addEdge(u, i);
	}
	buildTree();
	preAns();
	while (q --) {
		int r1, r2;
		readInt(r1);
		readInt(r2);
		if (bi[r1] > -1)
			printf(lld "\n", bn[bi[r1]][r2]);
		else if (bi[r2] > -1)
			printf(lld "\n", nb[bi[r2]][r1]);
		else
			printf(lld "\n", query(r1, r2));
	}
}