CF208E：Blood Cousins

#include <iostream>

const int oxis = 100002;
int xch[oxis], hch[oxis];	// XXX: 此种存法仅限有根树
int xqp[oxis], hqp[oxis];
int xqd[oxis], hqd[oxis];
int p[oxis], ans[oxis], cnt[oxis];
int sz[oxis], pr[oxis];

int input()
{
	int n, m;
	using std::cin;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int pa;
		cin >> pa;
		xch[i] = hch[pa];
		hch[pa] = i;
	}
	cin >> m;
	for (int i = 1; i <= m; ++i) {
		int v;
		cin >> v >> p[i];
		xqp[i] = hqp[v];
		hqp[v] = i;
	}
	return m;
}

void dfs1(int root, int de)
{
	for (int &i = hqp[root]; i; i = xqp[i]) {
		int dea = de - p[i];
		if (dea < 0)
			continue;
		xqd[i] = hqd[dea];
		hqd[dea] = i;
	}
	pr[root] = hch[root];
	sz[root] = 1;
	for (int i = hch[root]; i; i = xch[i]) {
		dfs1(i, 1 + de);
		sz[root] += sz[i];
		if (sz[i] > sz[pr[root]])
			pr[root] = i;
	}
	for (int &i = hqd[de]; i; i = xqd[i]) {
		xqp[i] = hqp[root];
		hqp[root] = i;
	}
}

template <int offset> void work(int root, int de)
{
	cnt[de] += offset;
	for (int i = hch[root]; i; i = xch[i])
		work<offset>(i, 1 + de);
}

template <bool keep> void dfs2(int root, int de)
{
	for (int i = hch[root]; i; i = xch[i])
		if (i != pr[root])
			dfs2<false>(i, 1 + de);
	if (pr[root])
		dfs2<true>(pr[root], 1 + de);
	cnt[de]++;
	for (int i = hch[root]; i; i = xch[i])
		if (i != pr[root])
			work<1>(i, 1 + de);
	if (root)
		for (int i = hqp[root]; i; i = xqp[i])
			ans[i] = cnt[de + p[i]] - 1;
	if (!keep)
		work< -1>(root, de);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int m = input();
	dfs1(0, 0);
	dfs2<true>(0, 0);
	for (int i = 1; i <= m; ++i)
		std::cout << ans[i] << ' ';
}