<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));
}

}