题意

题目链接

Sol

很神仙的题

我们考虑询问(a, b)(a是b的祖先)，直接对b根号分治

如果b的出现次数\(< \sqrt{n}\)，我们可以直接对每个b记录下与它有关的询问，这样每个询问至多扫\(\sqrt{n}\)个点即可知道答案，那么dfs的时候暴力统计答案即可，复杂度\(q\sqrt{n}\)

如果b的出现次数\(> \sqrt{n}\)，显然这样的b最多只有\(\sqrt{n}\)个，也就是说在询问中最多会有\(\sqrt{n}\)个这样的b，那么我们可以对每个a，暴力统计，复杂度\(n\sqrt{n}\)

然后用天天爱跑步那题的差分技巧搞一下就行了

代码十分好写~

#include<bits/stdc++.h>

#define Pair pair<int, int>

#define MP(x, y) make_pair(x, y)

#define fi first

#define se second

//#define int long long

#define LL long long

#define Fin(x) {freopen(#x".in","r",stdin);}

#define Fout(x) {freopen(#x".out","w",stdout);}

using namespace std;

const int MAXN = 1e6 + 10;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int N, R, Q, base;

vector<int> v[MAXN];

vector<Pair> a1[MAXN], a2[MAXN];

int r[MAXN], fa[MAXN], ti[MAXN], ha[MAXN], ans[MAXN];

void dfs1(int x) {

	for(auto &a : a1[r[x]]) ans[a.se] += ha[a.fi]; ha[r[x]]++;

	for(auto &to : v[x]) dfs1(to); ha[r[x]]--;

}

void dfs2(int x) {

	for(auto &b: a2[r[x]]) ans[b.se] -= ha[b.fi];

	for(auto &to: v[x]) dfs2(to);

	for(auto &b: a2[r[x]]) ans[b.se] += ha[b.fi];

	ha[r[x]]++;

}

signed main() {

//	Fin(9); Fout(b);

	N = read(); R = read(); Q = read(); base = sqrt(N);

	r[1] = read(); ti[r[1]]++;

	for(int i = 2; i <= N; i++) {

		int f = read(); r[i] = read();

		v[f].push_back(i);

		ti[r[i]]++;

	}

	for(int i = 1; i <= Q; i++) {

		int a = read(), b = read();

		if(ti[b] < base) {

			a1[b].push_back({a, i});

		} else {

			a2[a].push_back({b, i});

		}

	}

	dfs1(1);

	memset(ha, 0, sizeof(ha));

	dfs2(1);

	for(int i = 1; i <= Q; i++) printf("%d\n", ans[i]);

    return 0;

}