// Problem: D - Regions
// Contest: Virtual Judge - 2024-10-13 - 10/10 problems
// URL: https://vjudge.net/contest/661996#problem/D
// Memory Limit: 128 MB
// Time Limit: 8000 ms
//
// By Muaath Alqarni
// Blog: https://muaath5.githib.io/blog
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 2e5+1, R = 25001, SQ = 417, CSQ = N / SQ + 1;
int n, r, q, reg[N];
vector<int> adj[N];
vector<int> people[R];
// dfs tree
int ttt = 1, dt[N], ft[N];
void dfs(int node) {
dt[node] = ttt++;
for (int ch : adj[node]) {
dfs(ch);
}
ft[node] = ttt-1;
}
// small & big
int type[R]; // boolean 0=small, 1=big
int idx[R];
int big_any[CSQ][R];
int any_big[R][CSQ];
int srch = 0;
int sum[N];
void dfs2(int node) {
sum[node] = (reg[node] == srch);
for (int ch : adj[node]) {
dfs2(ch);
sum[node] += sum[ch];
}
}
int fakelazy[N] = {};
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> r >> q;
for (int i = 1; i <= n; i++) {
if (i != 1) {
int p;
cin >> p;
adj[p].push_back(i);
}
cin >> reg[i];
people[reg[i]].push_back(i);
}
dfs(1);
//cerr << 1ll * N * SQ*10 << ' ' << 1ll * N * CSQ << endl;
// precalc
int lstidx = 0;
for (int i = 1; i <= r; i++) {
type[i] = (people[i].size() >= SQ);
if (type[i]) {
idx[i] = lstidx++;
memset(fakelazy, 0, sizeof(fakelazy));
// precalculate
// big_any
for (int c : people[i]) {
fakelazy[dt[c]]++;
fakelazy[ft[c]+1]--;
}
for (int j = 1; j <= n; j++)
fakelazy[j] += fakelazy[j-1];
for (int j = 1; j <= n; j++)
big_any[idx[i]][reg[j]] += fakelazy[dt[j]];
// any_big
srch = i;
dfs2(1);
for (int j = 1; j <= n; j++)
any_big[reg[j]][idx[i]] += sum[j];
}
}
while (q--) {
int r1, r2;
cin >> r1 >> r2;
if (type[r1]) cout
#ifdef MUAATH_5
<< '#'
#endif
<< big_any[idx[r1]][r2] << endl;
else if (type[r2]) cout
#ifdef MUAATH_5
<< '*'
#endif
<< any_big[r1][idx[r2]] << endl;
else {
int sol = 0;
// optimize this with sweep-line
vector<array<int, 2>> evt;
evt.reserve(people[r1].size() * 2 + people[r2].size());
for (int c : people[r1]) {
evt.push_back({dt[c], 1});
evt.push_back({ft[c], 3});
}
for (int c : people[r2]) {
evt.push_back({dt[c], 2});
}
sort(evt.begin(), evt.end());
int cover = 0;
for (auto [x, t] : evt) {
if (t == 1) cover++;
if (t == 2) sol += cover;
if (t == 3) cover--;
}
cout << sol << endl;
}
}
}
