#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
const int MX = 200005;
struct FenwickTree {
vector<long long> bit; // binary indexed tree
int n = MX;
int sum(int r) {
if(bit.empty()) bit.resize(n);
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}
int sum(int l, int r) {
return sum(r) - sum(l - 1);
}
void add(int idx, int delta) {
if(bit.empty()) bit.resize(n);
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};
const int B = 50;
int N, R, Q;
vector <int> g[MX], region[MX];
int H[MX], st[MX], en[MX], timer=1, stwho[MX];
long long prep[5000][R+1];
void Flat(int v, int p) {
stwho[timer] = v;
st[v] = timer++;
region[H[v]].push_back(st[v]);
for(auto to : g[v]) if(to!=p) {
Flat(to, v);
}
en[v] = timer-1;
}
int main() {
cin >> N >> R >> Q;
cin >> H[1];
for(int i=2; i<=N; ++i) {
int p; cin >> p >> H[i];
g[p].push_back(i);
}
Flat(1, 1);
vector <int> bigs;
int index[R+1], cur=0;
for(int i=1; i<=R; ++i) if(region[i].size()>B) {
bigs.push_back(i);
index[i] = cur++;
}
FenwickTree A;
for(int all=1; all<=R; ++all) {
for(auto it : region[all]) {
A.add(st[it], 1);
}
for(auto b : bigs) {
for(auto it : region[index[b]]) {
prep[index[b]][all] += A.sum(st[it], en[it]);
}
}
for(auto it : region[all]) {
A.add(st[it], -1);
}
}
// O(Q(rootNlogN + logR))
while(Q--) {
int r1, r2;
cin >> r1 >> r2;
long long ans = 0;
if(region[r1].size()>B) {
ans = prep[index[r1]][r2];
} else {
for(auto p1 : region[r1]) {
auto it = upper_bound(region[r2].begin(), region[r2].end(), en[stwho[p1]]);
auto it2 = lower_bound(region[r2].begin(), region[r2].end(), p1);
ans += it-it2;
}
}
assert(ans>=0);
cout << ans << endl;
}
return 0;
}
Compilation message
regions.cpp:31:25: error: array bound is not an integer constant before ']' token
31 | long long prep[5000][R+1];
| ^
regions.cpp: In function 'int main()':
regions.cpp:63:5: error: 'prep' was not declared in this scope
63 | prep[index[b]][all] += A.sum(st[it], en[it]);
| ^~~~
regions.cpp:77:10: error: 'prep' was not declared in this scope
77 | ans = prep[index[r1]][r2];
| ^~~~
