#include <bits/stdc++.h>
using namespace std;
const int MAXR = 25000;
const int MAXN = 200000;
bool big[MAXR + 5];
vector<int>v[MAXR + 5], graph[MAXN + 5];
int n, r, q, region, a[MAXN + 5], in[MAXN + 5], out[MAXN + 5], timer, ans[MAXR + 5][MAXR + 5];
bool cmp(int x, int y){
return in[x] < in[y];
}
void dfs_tour(int node, int parent)
{
in[node] = ++timer;
for(auto i: graph[node])
{
if(i == parent)continue;
dfs_tour(i, node);
}
out[node] = ++timer;
}
void dfs(int node, int parent, int counter)
{
for(auto i: graph[node])
{
if(i == parent)continue;
if(a[node] == region)dfs(i, node, counter + 1);
else dfs(i, node, counter);
}
ans[region][a[node]] += counter;
}
void solve(int r1, int r2)
{
int counter = 0;
for(auto i: v[r1])
{
int l = 0, r = v[r2].size() - 1, ansl = -1, ansr = -1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(in[v[r2][mid]] > in[i])
{
ansl = mid;
r = mid - 1;
}
else l = mid + 1;
}
l = 0; r = v[r2].size() - 1;
while(l <= r)
{
int mid = l + (r - l) / 2;
if(in[v[r2][mid]] < out[i])
{
ansr = mid;
l = mid + 1;
}
else r = mid - 1;
}
if(ansl != -1 && ansr != -1)counter += ansr - ansl + 1;
}
cout << counter << endl;
}
signed main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr); std::cout.tie(nullptr);
cin >> n >> r >> q;
cin >> a[1];
for(int i = 2; i <= n; i++)
{
int par; cin >> par >> a[i];
graph[par].push_back(i);
}
dfs_tour(1, 0);
for(int i = 1; i <= n; i++)
{
v[a[i]].push_back(i);
}
for(int i = 1; i <= r; i++)
{
sort(v[i].begin(), v[i].end(), cmp);
if(v[i].size() > sqrt(n))
{
big[i] = true;
region = i; dfs(1, 0, 0);
}
}
while(q--)
{
int r1, r2; cin >> r1 >> r2;
if(big[r1])cout << ans[r1][r2] << endl;
else solve(r1, r2);
}
return 0;
}
Compilation message (stderr)
/usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(ios_init.o): in function `std::ios_base::Init::Init()':
(.text._ZNSt8ios_base4InitC2Ev+0x1f): failed to convert GOTPCREL relocation against '_ZNSt8ios_base4Init11_S_refcountE'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x66): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x71): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x7c): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xa0): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xab): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xc8): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xe1): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xf4): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cin_sync' defined in .bss._ZN14__gnu_internal12buf_cin_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0xfb): relocation truncated to fit: R_X86_64_PC32 against symbol `__gnu_internal::buf_cout_sync' defined in .bss._ZN14__gnu_internal13buf_cout_syncE section in /usr/lib/gcc/x86_64-linux-gnu/13/libstdc++.a(globals_io.o)
(.text._ZNSt8ios_base4InitC2Ev+0x101): additional relocation overflows omitted from the output
(.text._ZNSt8ios_base4InitC2Ev+0x1ed): failed to convert GOTPCREL relocation against '_ZSt4cout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x252): failed to convert GOTPCREL relocation against '_ZSt3cin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x2bc): failed to convert GOTPCREL relocation against '_ZSt4cerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x316): failed to convert GOTPCREL relocation against '_ZSt4clog'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x50f): failed to convert GOTPCREL relocation against '_ZSt5wcout'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x57d): failed to convert GOTPCREL relocation against '_ZSt4wcin'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x5f0): failed to convert GOTPCREL relocation against '_ZSt5wcerr'; relink with --no-relax
(.text._ZNSt8ios_base4InitC2Ev+0x654): failed to convert GOTPCREL relocation against '_ZSt5wclog'; relink with --no-relax
/usr/bin/ld: final link failed
collect2: error: ld returned 1 exit status
