#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
const int MAXN = 200000;
int n, r, m;
int st[MAXN+1], en[MAXN+1], timer = 0;
int country[MAXN+1];
vector<int> tree[MAXN+1];
// Lưu pair (st, en) cho mỗi node; sẽ sort theo st
vector<pair<int,int>> nodes_by_country[25001];
void dfs(int u) {
st[u] = ++timer;
for (int v : tree[u]) dfs(v);
en[u] = timer;
// sau khi có st[u] và en[u], lưu vào country
nodes_by_country[country[u]].emplace_back(st[u], en[u]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> r >> m;
for (int i = 1; i <= n; i++) {
if (i == 1) {
cin >> country[1];
} else {
int p;
cin >> p >> country[i];
tree[p].push_back(i);
}
}
dfs(1);
// với mỗi quốc gia, sort các pair theo st
for (int c = 1; c <= r; c++) {
auto &vec = nodes_by_country[c];
sort(vec.begin(), vec.end(), [](auto &a, auto &b){
return a.first < b.first;
});
}
while (m--) {
int A, B;
cin >> A >> B;
ll ans = 0;
auto &VA = nodes_by_country[A];
auto &VB = nodes_by_country[B];
// tách riêng mảng st của B để binary search
vector<int> stB;
stB.reserve(VB.size());
for (auto &pr : VB) stB.push_back(pr.first);
for (auto &pr : VA) {
int st_u = pr.first, en_u = pr.second;
// số v có st[v] >= st_u
auto itL = lower_bound(stB.begin(), stB.end(), st_u);
// số v có st[v] > en_u
auto itR = upper_bound(stB.begin(), stB.end(), en_u);
ans += (itR - itL);
}
cout << ans << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |