#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int S = 128;
const int N = 400'032 + S;
const int R = 25'010;
int reg[N];
int len = 0;
int exp_reg[N];
int delta[N];
vector<int> bl_regs[N/S];
int cnt[N/S][S+1];
int scnt[N/S][S+1];
short sum[N/S][S+1][S+1];
vector<int> A[N];
int n, r, q;
void dfs(int v)
{
exp_reg[len] = reg[v];
delta[len] = 1;
++len;
for (int u : A[v])
dfs(u);
exp_reg[len] = reg[v];
delta[len] = -1;
++len;
}
int compress(int i, int x)
{
auto it = lower_bound(bl_regs[i].begin(), bl_regs[i].end(), x);
if (it == bl_regs[i].end() || *it != x)
return S;
return it - bl_regs[i].begin();
}
void calc_block(int bl)
{
int l = bl*S, r = min(bl*S+S, len);
int ans[S][S] = {}, pre[S] = {};
Loop (i,l,r) {
int reg = exp_reg[i];
Loop (j,0,S)
ans[reg][j] += pre[j];
pre[reg] += delta[i];
}
Loop (i,0,S) Loop (j,0,S)
sum[bl][i][j] = ans[j][i];
}
void comp_block(int bl)
{
int l = bl*S, r = min(bl*S+S, len);
static int arr[R];
Loop (i,l,r)
bl_regs[bl].push_back(exp_reg[i]);
sort(bl_regs[bl].begin(), bl_regs[bl].end());
bl_regs[bl].resize( unique(bl_regs[bl].begin(), bl_regs[bl].end())
- bl_regs[bl].begin());
Loop (i,0,bl_regs[bl].size())
arr[bl_regs[bl][i]] = i;
Loop (i,l,r)
exp_reg[i] = arr[exp_reg[i]];
}
void init()
{
for (int l = 0; l < len; l += S)
{
int r = min(len, l + S);
comp_block(l/S);
calc_block(l/S);
Loop (i,l,r) {
cnt[l/S][exp_reg[i]]++;
scnt[l/S][exp_reg[i]] += delta[i];
}
}
}
int solve(int r1, int r2)
{
int ans = 0, pre = 0;
Loop (i,0,(len+S-1)/S) {
int cr1 = compress(i, r1);
int cr2 = compress(i, r2);
ans += pre * cnt[i][cr2];
ans += sum[i][cr1][cr2];
pre += scnt[i][cr1];
}
return ans/2;
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
cin >> n >> r >> q;
cin >> reg[0];
Loop (i,1,n) {
int p;
cin >> p >> reg[i];
A[p-1].push_back(i);
}
dfs(0);
init();
while (q--) {
int r1, r2;
cin >> r1 >> r2;
cout << solve(r1, r2) << '\n';
cout.flush();
}
}
