/**
* author minhnguyent546
* created_at Wed, 2025-01-01 16:52:58
* problem https://oj.uz/problem/view/IOI09_regions
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "cp/debug.h"
#else
#define debug(...)
#define cerr if (false) cerr
#endif
int n, r, q;
const int N = (int) 2e5 + 3;
const int R = (int) 25e3 + 3;
vector<int> g[N];
int house[N], par[N];
vector<int> vers[R];
int tin[N], tout[N];
int timer = 0;
void dfs(int u) {
tin[u] = timer++;
for (int v : g[u]) {
dfs(v);
}
tout[u] = timer - 1;
}
template<typename T>
struct Fenwick {
int n;
vector<T> tree;
Fenwick() {}
Fenwick(int _n): n(_n), tree(n) {}
void add(int i, T val) {
while (i < n) {
tree[i] += val;
i |= (i + 1);
}
}
T pref(int i) {
T res{};
while (i >= 0) {
res += tree[i];
i = (i & (i + 1)) - 1;
}
return res;
}
T query(int l, int r) { return pref(r) - pref(l - 1); }
};
void read_input() {
cin >> n >> r >> q;
cin >> house[0];
--house[0];
for (int i = 1; i < n; ++i) {
int x, h;
cin >> x >> h;
--x; --h;
par[i] = x;
g[x].emplace_back(i);
house[i] = h;
}
for (int i = 0; i < n; ++i) {
vers[house[i]].emplace_back(i);
}
}
namespace sub1 {
bool check() {
return r <= 500;
}
void solve() {
dfs(0);
vector<vector<int>> cnt(r, vector<int>(r));
Fenwick<int> tree(n);
for (int r1 = 0; r1 < r; ++r1) {
for (int r2 = 0; r2 < r; ++r2) {
if (r2 == r1) continue;
for (int ver : vers[r2]) {
tree.add(tin[ver], 1);
}
for (int ver : vers[r1]) {
cnt[r1][r2] += tree.query(tin[ver] + 1, tout[ver]);
}
// reset
for (int ver : vers[r2]) {
tree.add(tin[ver], -1);
}
}
}
for (int w = 0; w < q; ++w) {
int r1, r2;
cin >> r1 >> r2;
--r1; --r2;
cout << cnt[r1][r2] << endl;
}
}
void solve2() {
dfs(0);
vector<vector<int>> cnt(r, vector<int>(r));
vector<int> pref(n + 3);
for (int r1 = 0; r1 < r; ++r1) {
fill(pref.begin(), pref.end(), 0);
for (int ver : vers[r1]) {
++pref[tin[ver] + 1];
--pref[tout[ver] + 1];
}
for (int i = 1; i <= n; ++i) {
pref[i] += pref[i - 1];
}
for (int r2 = 0; r2 < r; ++r2) {
if (r2 == r1) continue;
for (int ver : vers[r2]) {
cnt[r1][r2] += pref[tin[ver]];
}
}
}
for (int w = 0; w < q; ++w) {
int r1, r2;
cin >> r1 >> r2;
--r1; --r2;
cout << cnt[r1][r2] << endl;
}
}
} // namespace sub1
namespace sub2 {
bool check() {
for (int i = 0; i < r; ++i) {
if ((int) vers[i].size() > 500) return false;
}
return true;
}
void solve() {
dfs(0);
Fenwick<int> tree(n);
for (int w = 0; w < q; ++w) {
int r1, r2;
cin >> r1 >> r2;
--r1; --r2;
assert(r1 != r2);
for (int ver : vers[r2]) {
tree.add(tin[ver], 1);
}
int ans = 0;
for (int ver : vers[r1]) {
ans += tree.query(tin[ver] + 1, tout[ver]);
}
// reset
for (int ver : vers[r2]) {
tree.add(tin[ver], -1);
}
cout << ans << endl;
}
}
} // namespace sub2
namespace sub3 {
#ifdef LOCAL
const int THRESSHOLD = 2;
#else
const int THRESSHOLD = 450;
#endif
const int NUM_LARGES = 450 + 3;
int cnt_large_large[NUM_LARGES][NUM_LARGES];
int pref_for_small_large[NUM_LARGES][N + 3];
int pref_for_large_small[NUM_LARGES][N + 3];
bool check() {
return true;
}
void solve() {
dfs(0);
vector<int> large_idx(r, -1);
vector<int> who;
int num_larges = 0;
for (int i = 0; i < r; ++i) {
if ((int) vers[i].size() > THRESSHOLD) {
large_idx[i] = num_larges++;
who.emplace_back(i);
}
}
Fenwick<int> tree(n);
// assert(num_larges <= 400);
for (int i = 0; i < num_larges; ++i) {
int r1 = who[i];
for (int j = 0; j < num_larges; ++j) {
int r2 = who[j];
if (r1 == r2) continue;
for (int ver : vers[r2]) {
tree.add(tin[ver], 1);
}
for (int ver : vers[r1]) {
cnt_large_large[i][j] += tree.query(tin[ver] + 1, tout[ver]);
}
// reset
for (int ver : vers[r2]) {
tree.add(tin[ver], -1);
}
}
}
for (int i = 0; i < num_larges; ++i) {
for (int v : vers[who[i]]) {
pref_for_small_large[i][tin[v] + 1]++;
}
for (int j = 1; j <= n; ++j) {
pref_for_small_large[i][j] += pref_for_small_large[i][j - 1];
}
}
for (int i = 0; i < num_larges; ++i) {
for (int v : vers[who[i]]) {
pref_for_large_small[i][tin[v] + 1]++;
pref_for_large_small[i][tout[v] + 1]--;
}
for (int j = 1; j <= n; ++j) {
pref_for_large_small[i][j] += pref_for_large_small[i][j - 1];
}
}
for (int w = 0; w < q; ++w) {
int r1, r2;
cin >> r1 >> r2;
--r1; --r2;
assert(r1 != r2);
int ans = 0;
if (large_idx[r1] != -1 && large_idx[r2] != -1) {
// both r1 and r2 are large
ans = cnt_large_large[large_idx[r1]][large_idx[r2]];
} else if (large_idx[r1] != -1) {
// r1 is large, r2 is small
for (int ver : vers[r2]) {
ans += pref_for_large_small[large_idx[r1]][tin[ver]];
}
} else if (large_idx[r2] != -1) {
// r1 is small, r2 is large
for (int ver : vers[r1]) {
ans += pref_for_small_large[large_idx[r2]][tout[ver] + 1] - pref_for_small_large[large_idx[r2]][tin[ver] + 1];
}
} else {
// both r1 and r2 are small
for (int ver : vers[r2]) {
tree.add(tin[ver], 1);
}
for (int ver : vers[r1]) {
ans += tree.query(tin[ver] + 1, tout[ver]);
}
// reset
for (int ver : vers[r2]) {
tree.add(tin[ver], -1);
}
}
cout << ans << endl;
}
}
} // namespace sub3
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
read_input();
#ifdef LOCAL
// sub1::solve2();
sub3::solve();
return 0;
#endif
if (sub1::check()) {
sub1::solve2();
return 0;
}
if (sub2::check()) {
sub2::solve();
return 0;
}
if (sub3::check()) {
sub3::solve();
return 0;
}
assert(false);
return 0;
}
