#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define l int
int read(){
char x = getchar();
int val = 0;
while(x<'0'||x>'9')x=getchar();
while('0'<=x&&x<='9')
val = val*10+x-'0', x=getchar();
return val;
}
using namespace std;
vector<l> adj[200001];
vector<pair<l,l>> arr[25001];
l region[200001], t, ans1[21][25001], ans2[25001][21], in[200001], out[200001], li[200001], sz[25001], lg[21];
void merge(unordered_map<l, l> &a, unordered_map<l, l> b){
if(a.size()<b.size())
swap(a, b);
for(auto i: b)
a[i.first]+=i.second;
}
unordered_map<l,l> dfs(l n){
unordered_map<l,l> cur;
cur[region[n]]=1;
in[n]=t++;
arr[region[n]].push_back({in[n],1});
for(auto i: adj[n]){
merge(cur, dfs(i));
}
out[n]=t++;
arr[region[n]].push_back({out[n],-1});
if(li[region[n]])
for(auto i: cur)
ans1[li[region[n]]][i.first]+=i.second;
else
for(auto i: lg)
ans2[region[n]][li[i]]+=cur[i];
return cur;
}
l query_s(int r1, int r2){
l sum=0, o=0, a=0, b=0;
while(a<arr[r1].size()&&b<arr[r2].size()){
if(arr[r1][a]<arr[r2][b])
o+=arr[r1][a].second, a++;
else
sum+=o, b++;
}
return sum/2;
}
int main(){
l n=read(), r=read(), q=read(), lr=0;
region[1]=read();
for(l i = 2; i <= n; i++){
adj[read()].push_back(i);
region[i] = read();
sz[region[i]]++;
}
for(int i = 1; i <= r; i++)
if(sz[i]>10000)
lg[lr]=i, li[i]=++lr;
dfs(1);
while(q--){
int r1=read(), r2=read();
if(li[r1])
cout << ans1[li[r1]][r2] << endl;
else if(li[r2])
cout << ans2[r1][li[r2]] << endl;
else
cout << query_s(r1, r2) << endl;
}
Compilation message
regions.cpp: In function 'int query_s(int, int)':
regions.cpp:42:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | while(a<arr[r1].size()&&b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp:42:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | while(a<arr[r1].size()&&b<arr[r2].size()){
| ~^~~~~~~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:70:5: error: expected '}' at end of input
70 | }
| ^
regions.cpp:50:11: note: to match this '{'
50 | int main(){
| ^
