<div class="post_brief"><p>
ioi的数据结构题，果然还是比较BT的。</p>

 

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

 

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

#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 &lt;= 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] &gt; -1)
		printf(lld "\n", bn[bi[r1]][r2]);
	else if (bi[r2] &gt; -1)
		printf(lld "\n", nb[bi[r2]][r1]);
	else
		printf(lld "\n", query(r1, r2));
}



}