#include<bits/stdc++.h>
using namespace std;
#define debug(...) 42
#define int long long
using ll = long long;
const int maxn = 2e5 + 1;
vector<int> ad[maxn], comp[25001];
int tin[maxn], tout[maxn], ord[maxn], a[25001], id[25001], timeDfs = 0;
vector<vector<int>> calc;
void tour(int u){
tin[u] = timeDfs++;
ord[tin[u]] = u;
comp[a[u]].push_back(tin[u]);
for (auto v : ad[u]) tour(v);
tout[u] = timeDfs;
}
void dfs(int u, int par_reg, int par_cnt){
if (a[u] == par_reg) par_cnt++;
calc[id[par_reg]][a[u]] += par_cnt;
for (auto v : ad[u]) dfs(v, par_reg, par_cnt);
}
void solve(){
int n, r, q;
cin >> n >> r >> q;
cin >> a[0];
a[0]--;
for (int i = 1; i < n; i++){
int p, h;
cin >> p >> h;
p--;
h--;
ad[p].push_back(i);
a[i] = h;
}
for (int i = 0; i < r; i++) id[i] = -1;
tour(0);
int cur = 0;
const int block = sqrt(n);
for (int i = 0; i < r; i++){
if (comp[i].size() >= block){
id[i] = cur++;
calc.push_back(vector<int> (r));
dfs(0, i, 0);
}
}
while(q--){
int e1, e2;
cin >> e1 >> e2;
e1--, e2--;
if (comp[e1].size() >= block){
cout << calc[id[e1]][e2] << "\n";
}
else{
int ans = 0;
for (auto u : comp[e1]){
ans += lower_bound(comp[e2].begin(), comp[e2].end(), tout[ord[u]])
- lower_bound(comp[e2].begin(), comp[e2].end(), tin[ord[u]]);
}
cout << ans << "\n";
}
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |