/**
____ ____ ____ __________________ ____ ____ ____
||I || ||c || ||e || || || ||M || ||a || ||n ||
||__|| ||__|| ||__|| ||________________|| ||__|| ||__|| ||__||
|/__\| |/__\| |/__\| |/________________\| |/__\| |/__\| |/__\|
*/
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define maxn 200005
#define maxr 25005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;
using namespace std;
typedef long long ll;
typedef pair <ll , ll> pll;
typedef pair <int , int> pii;
typedef long double ld;
typedef unsigned long long ull;
map <int , int> br[maxn];
int n , r , q;
vector <int> v[maxn];
int color[maxn];
vector <int> c[maxr];
int ans[maxr][maxr];
int sz[maxn] , id[maxn];
int pre[maxn];
int timer;
vector <int> tt[maxn];
void dfs(int node , int par)
{
id[node] = timer;
pre[timer] = color[node];
sz[node] = 1;
tt[color[node]].pb(timer);
timer++;
for(auto& nb : v[node])
{
if(nb == par)
continue;
dfs(nb , node);
sz[node] += sz[nb];
}
}
bool used[maxn];
void dfs2(int node , int par , int br , int col)
{
if(color[node] == col)
used[node] = true;
ans[col][color[node]] += br;
for(auto& nb : v[node])
dfs2(nb , node , br + (col == color[node]) , col);
}
int par[maxn];
void read()
{
cin >> n >> r >> q;
for(int i = 1; i <= n; i++)
{
if(i == 1)
{
cin >> color[i];
c[color[i]].pb(i);
continue;
}
int x;
cin >> par[i] >> color[i];
c[color[i]].pb(i);
v[par[i]].pb(i);
v[i].pb(par[i]);
}
int sq = 500;
timer = 0;
dfs(1 , 0);
for(int i = 1; i <= r; i++)
if(c[i].size() > 500)
for(auto& e : c[i])
if(used[e] == false)
dfs2(e , par[e] , 0 , color[e]);
int x , y;
while(q--)
{
cin >> x >> y;
if(c[x].size() > 500)
{
cout << ans[x][y] << endl;
cout.flush();
continue;
}
int curr = 0;
for(auto& e : c[x])
curr += (upper_bound(tt[y].begin() , tt[y].end() , id[e] + sz[e] - 1) - tt[y].begin())
- (lower_bound(tt[y].begin() , tt[y].end() , id[e]) - tt[y].begin());
cout << curr << endl;
cout.flush();
}
}
int main()
{
/**#ifdef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif*/
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
///startT = std::chrono::high_resolution_clock::now();
read();
return 0;
}
Compilation message
regions.cpp: In function 'void read()':
regions.cpp:101:13: warning: unused variable 'x' [-Wunused-variable]
101 | int x;
| ^
regions.cpp:109:9: warning: unused variable 'sq' [-Wunused-variable]
109 | int sq = 500;
| ^~
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
