#ifndef LOCAL
#include "regions.h"
#endif // LOCAL
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#define pb push_back
#define mp make_pair
#define taskname "A"
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 2e5 + 5;
const int maxr = 25005;
const int MAGIC = 505;
int n , r , q;
int col[maxn];
vector<int> adj[maxn];
int in[maxn] , out[maxn] , rv[maxn];
int PRECAL_ANS[maxr][MAGIC];
int PRECAL_ANS1[MAGIC][maxr];
vector<int> gr[maxr];
int cnt1[maxr];
int BIG = 0;
int id[maxr];
map<int,int> *mmap[maxn];
int sub[maxn];
void dfs1(int u){
sub[u] = 1;
for(auto &c : adj[u]){
dfs1(c);
sub[u] += sub[c];
if(sub[c] > sub[adj[u][0]])swap(c,adj[u][0]);
}
}
void dfs(int u){
static int nTime = 0;
in[u] = ++nTime;
rv[nTime] = u;
if(id[col[u]] != -1)cnt1[id[col[u]]]++;
for(int j = 0 ; j < BIG ; ++j){
PRECAL_ANS1[j][col[u]] += cnt1[j];
assert(PRECAL_ANS1[j][col[u]] <= 1e9);
}
for(auto c : adj[u]){
dfs(c);
}
if(adj[u].size() == 0)mmap[u] = new map<int,int>();
else mmap[u] = mmap[adj[u][0]];
for(auto c : adj[u]){
if(c != adj[u][0]){
for(auto d : (*mmap[c])){
(*mmap[u])[d.first] += d.second;
}
}
}
if(id[col[u]] != -1){
cnt1[id[col[u]]]--;
(*mmap[u])[id[col[u]]]++;
}
for(auto c : (*mmap[u])){
PRECAL_ANS[col[u]][c.first] += c.second;
// assert(PRECAL_ANS[col[u]][c.first] <= 1e9);
}
out[u] = nTime;
}
void init(int N, int R, int Q, int S[], int H[]) {
n = N;r = R;
for(int i = 0 ; i < n ; ++i){
col[i + 1] = H[i];
if(i > 0)adj[S[i]].pb(i + 1);
gr[col[i + 1]].pb(i + 1);
}
memset(id,-1,sizeof id);
int cnt = 0;
for(int i = 1 ; i <= r ; ++i){
if(gr[i].size() >= MAGIC){
id[i] = BIG++;
}
}
dfs1(1);
dfs(1);
for(int i = 1 ; i <= r ; ++i){
for(auto & c : gr[i])c = in[c];
sort(gr[i].begin(),gr[i].end());
}
return;
}
int query(int r1, int r2) {
if(id[r2] != -1)return PRECAL_ANS[r1][id[r2]];
if(id[r1] != -1)return PRECAL_ANS1[id[r1]][r2];
int res = 0;
for(auto & c : gr[r1]){
int & tmp = rv[c];
res += upper_bound(gr[r2].begin(),gr[r2].end(),out[tmp])
-lower_bound(gr[r2].begin(),gr[r2].end(),in[tmp]);
}
// assert(res >= 0);
return res;
}
#ifdef LOCAL
#include <vector>
#include <cstdio>
using namespace std;
int N,Q,R;
int H[200005];
int S[200005];
int ans[200005];
int main () {
freopen("A.INP","r",stdin);
freopen("A.OUT","w",stdout);
scanf("%d%d%d", &N, &R, &Q);
scanf("%d", &H[0]);
S[0] = -1;
for (int i = 1; i < N; i++) {
scanf("%d%d", &S[i], &H[i]);
}
init(N,R,Q,S,H);
for (int i = 0; i < Q; i++) {
int r1,r2;
scanf("%d%d", &r1, &r2);
cout << query(r1,r2) << '\n';
}
return 0;
}
#endif // LOCAL
Compilation message
regions.cpp:2:10: fatal error: regions.h: No such file or directory
#include "regions.h"
^~~~~~~~~~~
compilation terminated.
