#include <bits/stdc++.h>
using namespace std;
struct node{
int l, r, num;
vector<int> child;
int reg;
};
int R;
void dfs(int head, vector<node> &tree, int &c){
tree[head].l = c;
for(int i : tree[head].child){
dfs(i, tree, c);
}
tree[head].r = c;
tree[head].num = c++;
}
struct node2{
vector<short> arr;
vector<int> child;
int reg;
};
void dfs2(int head, vector<node2> &tree){
for(int i : tree[head].child){
dfs(i, tree);
for(int j = 0; j < R; j ++){
tree[head].arr[j] += tree[i].arr[j];
}
}
tree[head].arr[tree[head].reg]++;
}
int main()
{
int N, Q;
cin >> N >> R >> Q;
if(R< 500){
vector<node2> tree(N);
cin >> tree[0].reg;
tree[0].reg--;
tree[0].arr.assign(R, 0);
for(int i = 1; i < N; i ++){
tree[i].arr.assign(R, 0);
int a, b;
cin >> a >> b;
a--;
b--;
tree[a].child.push_back(i);
tree[i].reg = b;
}
vector<vector<int>> table(R, vector<int> (R));
dfs2(0, tree);
for(auto j : tree){
for(int i = 0; i < R; i ++){
table[j.reg][i] += j.arr[i];
}
}
while(Q--){
int a, b;
cin >> a >> b;
a--;b--;
cout << table[a][b] << endl;
}
}
else{
vector<node> tree(N);
cin >> tree[0].reg;
tree[0].reg--;
for(int i = 1; i < N; i ++){
int a, b;
cin >> a >> b;
a--;
b--;
tree[a].child.push_back(i);
tree[i].reg = b;
}
int c = 0;
dfs(0, tree, c);
vector<vector<int>> regions(R);
vector<vector<pair<int, int>>> ranges(R);
for(node i : tree){
regions[i.reg].push_back(i.num);
ranges[i.reg].push_back({i.l,i.r});
}
for(int i = 0; i < R; i ++){
sort(ranges[i].begin(), ranges[i].end());
sort(regions[i].begin(), regions[i].end());
}
while(Q--){
int a, b;
cin >> a >> b;
a--;b--;
int last = 0, lid = 0, cc = 0;
for(auto [l, r] : ranges[a]){
cc += upper_bound(regions[b].begin(), regions[b].end(), r)-regions[b].begin();
cc -= lower_bound(regions[b].begin(), regions[b].end(), l)-regions[b].begin();
}
cout << cc << endl;
}
}
return 0;
}
Compilation message
regions.cpp: In function 'void dfs2(int, std::vector<node2>&)':
regions.cpp:24:16: error: invalid initialization of reference of type 'std::vector<node>&' from expression of type 'std::vector<node2>'
24 | dfs(i, tree);
| ^~~~
regions.cpp:9:34: note: in passing argument 2 of 'void dfs(int, std::vector<node>&, int&)'
9 | void dfs(int head, vector<node> &tree, int &c){
| ~~~~~~~~~~~~~~^~~~
regions.cpp: In function 'int main()':
regions.cpp:91:17: warning: unused variable 'last' [-Wunused-variable]
91 | int last = 0, lid = 0, cc = 0;
| ^~~~
regions.cpp:91:27: warning: unused variable 'lid' [-Wunused-variable]
91 | int last = 0, lid = 0, cc = 0;
| ^~~
