#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for (long long i = a; i < b; i++)
#define sz(x) static_cast<long long>((x).size())
#define all(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#include "debug.h"
#endif
// #define int long long
#define double long double
const long long inf = (long long) 1e18;
const int mod = (int) 998244353;
signed main(){
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout << fixed << setprecision(10);
int n, r, q; cin >> n >> r >> q;
vector<vector<int>> adj(n);
vector<int> color[r];
vector<int> region(n);
vector<int> regiontotime[r];
cin >> region[0]; region[0]--;
color[region[0]].push_back(0);
rep(i, 1, n){
int y; cin >> y >> region[i];
y--; region[i]--;
adj[y].push_back(i);
color[region[i]].push_back(i);
}
vector<int> pc;
rep(i, 0, r) if(sz(color[i])*sz(color[i]) >= n) pc.push_back(i);
map<pair<int, int>, int> precomp;
vector<int> in(n, 0), out(n, 0), szz(n, 1);
int time = 0;
function<void(int, int)> dfs = [&](int v, int p){
in[v] = time++;
regiontotime[region[v]].push_back(in[v]);
for(auto child: adj[v]){
dfs(child, v);
szz[v] += szz[child];
}
out[v] = time++;
};
dfs(0, -1);
for(auto u: pc){
for(auto v: pc){
if(u == v) continue;
for(auto val: color[u]){
precomp[{u, v}] += upper_bound(all(regiontotime[region[v]]), out[val]) - lower_bound(all(regiontotime[region[v]]), in[val]);
}
}
}
while(q--){
int u, v; cin >> u >> v; u--; v--;
if(precomp.find({u, v}) != precomp.end()) cout << precomp[{u, v}] << endl;
else{
int res = 0;
for(auto val: color[u]) res += upper_bound(all(regiontotime[region[v]]), out[val]) - lower_bound(all(regiontotime[region[v]]), in[val]);
cout << res << endl;
}
}
}
Compilation message
regions.cpp:9:10: fatal error: debug.h: No such file or directory
9 | #include "debug.h"
| ^~~~~~~~~
compilation terminated.
