#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int rt=448;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[200000], sum2[200000], tree[200001];
long long ans[200000/rt+1][25000], ans2[200000/rt+1][25000];
char buf[MAX_SIZE];
inline int get_int()
{
int ret=0;
bool is_negative=false;
char c=-1;
while(!('0'<=c && c<='9') && c!='-') c=getchar_unlocked();
if(c=='-') {
is_negative=true;
c=getchar_unlocked();
}
while('0'<=c && c<='9') ret*=10, ret+=c-'0', c=getchar_unlocked();
return (is_negative ? -ret:ret);
}
void add_tree(int n, int v)
{
for(++n;n<=200000;n+=n&-n) tree[n]+=v;
}
int get_sum(int n)
{
int ret=0;
for(++n;n;n-=n&-n) ret+=tree[n];
return ret;
}
int get_sum(int s, int e)
{
return get_sum(e)-get_sum(s-1);
}
void dfs(int c)
{
num[c]=++node_cnt;
for(auto n: adj[c]) dfs(n);
fin[c]=node_cnt;
}
void dfs2(int c, int v)
{
sum[c]+=RV[c]==v;
sum2[c]=RV[c]==v;
for(auto n: adj[c]) {
sum[n]=sum[c];
dfs2(n,v);
sum2[c]+=sum2[n];
}
}
int main()
{
int N=get_int(), M=get_int(), Q=get_int(), p;
R[RV[0]=get_int()-1].push_back(0);
for(int i=1;i<N;i++) {
adj[get_int()-1].push_back(i);
R[RV[i]=get_int()-1].push_back(i);
}
dfs(0);
for(int i=0;i<M;i++) if(R[i].size()>=rt) {
sum[0]=0;
dfs2(0,i);
for(int j=0;j<N;j++) {
ans[O.size()][RV[j]]+=sum[j];
ans2[O.size()][RV[j]]+=sum2[j];
}
O.push_back(i);
}
while(Q--) {
int a=get_int()-1, b=get_int()-1;
if(R[a].size()>=rt) printf("%lld\n",ans[lower_bound(O.begin(),O.end(),a)-O.begin()][b]);
else if(R[b].size()>=rt) printf("%lld\n",ans2[lower_bound(O.begin(),O.end(),b)-O.begin()][a]);
else {
long long ans=0;
for(auto r: R[b]) add_tree(num[r],1);
for(auto r: R[a]) ans+=get_sum(num[r],fin[r]);
for(auto r: R[b]) add_tree(num[r],-1);
printf("%lld\n",ans);
}
fflush(stdout);
}
return 0;
}
Compilation message
regions.cpp:12:10: error: 'MAX_SIZE' was not declared in this scope
char buf[MAX_SIZE];
^~~~~~~~
regions.cpp:12:10: note: suggested alternative: '_T_SIZE'
char buf[MAX_SIZE];
^~~~~~~~
_T_SIZE
regions.cpp: In function 'int main()':
regions.cpp:65:45: warning: unused variable 'p' [-Wunused-variable]
int N=get_int(), M=get_int(), Q=get_int(), p;
^
