#include<bits/stdc++.h>
using namespace std;
struct mergeSortTree{
int N,n;
vector<vector<int>>tree;
void build(int v,int l,int r,vector<int>&a){
if(l>=n) return;
if(r-l==1){
tree[v]={a[l]};
return;
}
int mid=(l+r)/2;
build(v<<1,l,mid,a);
build(v<<1|1,mid,r,a);
merge(tree[v<<1].begin(),tree[v<<1].end(),tree[v<<1|1].begin(),tree[v<<1|1].end(),back_inserter(tree[v]));
}
mergeSortTree(vector<int>&a){
n=(int)a.size();
N=1;
while(N<n) N<<=1;
tree.resize(2*N);
build(1,0,N,a);
}
// void update(int v,int l,int r,int id,int x){
// cout<<v;
// if(r-l==1){
// tree[v]+=x;
// return;
// }
// int mid=(l+r)/2;
// if(mid>id) update(v<<1,l,mid,id,x);
// else update(v<<1|1,mid,r,id,x);
// tree[v]=tree[v<<1]+tree[v<<1|1];
// }
// void update(int id,int x){
// return update(1,0,N,id,x);
// }
int get(int v,int l,int r,int ql,int qr,int x){
if(ql>=r || l>=qr) return 0;
if(l>=ql && qr>=r) return lower_bound(tree[v].begin(),tree[v].end(),x+1)-lower_bound(tree[v].begin(),tree[v].end(),x);
int mid=(l+r)/2;
return get(v<<1,l,mid,ql,qr,x)+get(v<<1|1,mid,r,ql,qr,x);
}
int get(int l,int r,int x){
return get(1,0,N,l,r,x);
}
};
int n,r,q,timer = 0;
vector<int>h,tin,tout,b,r_id;
vector<vector<int>>v,a,dp;
vector<vector<int>>calc;
void dfs(int x){
tin[x]=timer++;
b.push_back(h[x]);
for(int z:v[x]){
dfs(z);
}
tout[x]=timer;
}
void dfs1(int x,int p_id,int p_c){
calc[r_id[p_id]][h[x]]+=p_c;
if(h[x]==p_id) p_c++;
for(int z:v[x]){
dfs1(z,p_id,p_c);
}
}
/*
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2
1 3
2 3
3 1
*/
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>r>>q;
h.resize(n+1);
a.resize(r+1);
cin>>h[1];
v.assign(n+1,vector<int>(0));
// dp.assign(r+1,vector<int>(r+1,-1));
for(int i=2,x;i<=n;i++){
cin>>x>>h[i];
v[x].push_back(i);
}
for(int i=1;i<=n;i++){
a[h[i]].push_back(i);
}
tin.resize(n+1);
tout.resize(n+1);
dfs(1);
// mergeSortTree S(b);
r_id.assign(r+1,-1);
int cur=-1;
const int BLOCK=(int)sqrt(n);
for(int i=1;i<=r;i++){
if(a[i].size()>=BLOCK){
r_id[i]=++cur;
calc.push_back(vector<int>(r+1));
dfs1(1,i,0);
}
}
while(q--){
int r1,r2;
cin>>r1>>r2;
if(r_id[r1]>-1){
cout<<calc[r_id[r1]][r2]<<'\n';
}
else{
int ans=0;
for(int x:a[r1]){
ans+=S.get(tin[x],tout[x],r2);
}
cout<<ans<<'\n';
}
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:121:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
121 | if(a[i].size()>=BLOCK){
| ~~~~~~~~~~~^~~~~~~
regions.cpp:136:22: error: 'S' was not declared in this scope
136 | ans+=S.get(tin[x],tout[x],r2);
| ^
