#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <functional>
#include <set>
//18:26
using namespace std;
using i64 = long long;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, r, q;
std::cin >> n >> r >> q;
std::vector<std::vector<int> > g(n + 1);
std::vector<int> reg(n + 1);
std::cin >> reg[1];
for (int i = 2; i <= n; i++) {
int h;
std::cin >> h;
std::cin >> reg[i];
g[h].push_back(i);
}
std::vector<std::vector<int> > ind(r + 1);
for (int i = 1; i <= n; i++) ind[reg[i]].push_back(i);
std::vector<pair<int, int> > xd(n + 1);
vector<int> tree;
int timer = 0;
std::function<void(int, int)> dfs1 = [&](const int u, const int v) {
xd[u].first = timer;
tree.push_back(reg[u]);
for (auto &d: g[u]) {
if (d != v) {
timer++;
dfs1(d, u);
}
}
xd[u].second = timer;
};
dfs1(1, -1);
std::vector<std::vector<int> > times(r + 1);
for (int i = 1; i <= n; i++) {
times[reg[i]].push_back(xd[i].first);
}
for (int i = 1; i <= r; i++) {
sort(times[i].begin(), times[i].end());
}
constexpr int B = 30;
vector<int> indexes(n + 1), trr(n + 1);
int it = 0;
for (int i = 1; i <= r; i++) {
if (ind[i].size() >= B) {
indexes[i] = it;
trr[it] = i;
it++;
}
}
vector<vector<i64>> total(r + 1, vector<i64>(it, 0));
std::vector<std::vector<i64>> mp(n + 1, vector<i64>(it, 0));
std::function<void(int, int)> dfs2 = [&](const int u, const int v) {
if (ind[u].size() >= B) mp[u][indexes[reg[u]]]++;
for (const auto &d: g[u]) {
if (d != v) {
for (int i = 0; i < it; i++) {
mp[d][i] += mp[u][i];
}
dfs2(d, u);
}
}
};
dfs2(1, -1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < it; j++) {
total[reg[i]][j] += mp[i][j];
}
}
for (int i = 0; i < q; i++) {
int r1, r2;
std::cin >> r1 >> r2;
if (ind[r1].size() >= B) {
std::cout << total[r2][indexes[r1]] << "\n";
cout.flush();
} else {
i64 answer = 0;
for (auto &d: ind[r1]) {
auto [l, r] = xd[d];
answer += upper_bound(times[r2].begin(), times[r2].end(), r) - lower_bound(
times[r2].begin(), times[r2].end(), l);
}
std::cout << answer << '\n';
cout.flush();
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |