#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MXN = 2e5+5, MXR = 25e3+4, sq = 110, sqi = MXN/sq+5;
int n, R, q, H[MXN], stt[MXN], fnt[MXN], timer;
vector<int> g[MXN], pos[MXR], posv[MXR];
int posbig[MXR];
vector<pii> vec[MXR];
int dp[sqi][sqi];
void dfs(int v) {
vec[H[v]].push_back(pii(stt[v]=timer++, vec[H[v]].empty() ? 1 : vec[H[v]].back().second+1));
pos[H[v]].push_back(stt[v]);
posv[H[v]].push_back(v);
for(int u : g[v]) dfs(u);
vec[H[v]].push_back(pii(fnt[v]=timer++, vec[H[v]].empty() ? -1 : vec[H[v]].back().second-1));
}
int dfs2(int v, int r) {
int sz = H[v]==r;
for(int u : g[v]) sz += dfs2(u, r);
if(H[v]!=r && pos[H[v]].size()>=sq) dp[posbig[H[v]]][posbig[r]] += sz;
return sz;
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n >> R >> q;
cin >> H[1];
for(int i=2, p; i<=n; i++) {
cin >> p >> H[i];
g[p].push_back(i);
}
dfs(1);
timer = 0;
for(int i=1; i<=R; i++)
if(pos[i].size()>=sq)
posbig[i] = timer++;
for(int i=1; i<=R; i++)
if(pos[i].size()>=sq)
dfs2(1, i);
while(q--) {
int r1, r2;
cin >> r1 >> r2;
if(pos[r1].size()<sq) {
int ans = 0;
for(int v : posv[r1])
ans += lower_bound(pos[r2].begin(), pos[r2].end(), fnt[v])
- lower_bound(pos[r2].begin(), pos[r2].end(), stt[v]);
cout << ans << endl;
}
else if(pos[r2].size()<sq) {
int ans = 0;
for(int v : posv[r2]) {
int ps = lower_bound(vec[r1].begin(), vec[r1].end(), pii(stt[v]+1, 0))-vec[r1].begin();
if(ps>0) ans += vec[r1][ps-1].second;
}
cout << ans << endl;
}
else cout << dp[posbig[r1]][posbig[r2]] << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |