Untitled

mail@pastecode.io avatar
unknown
c_cpp
7 months ago
3.1 kB
0
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 1e5 + 7;
const ll inf  = 1e15;

#define ios ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0)
#define pb(x) push_back(x)
#define all(x) sort(x.begin() , x.end())

void dbg(){
     cerr << endl;
}

template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

#define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)

int n , m , q , timer , lg , st[maxn] , ft[maxn] , dis[maxn];
vector<int> vec[maxn] , adj[maxn] , res , p;
bool mark[maxn];
int dad[20][maxn];

bool check(int v , int par){ 
     //er(st[par] , st[v] , ft[v] , ft[par]);    
     if(st[par] < st[v] && st[v] < ft[v] && ft[v] < ft[par])
          return true;
      return false;    
}
int ht(int x , int k){
     for(int i = 0 ; i <= lg ; i++){
          if(k >= (1 << i)){
               x = dad[i][x];
               k -= (1 << i);
          }
     }
     return x;
}
void query(){
     cin >> q;
     for(int i = 0 ; i < q ; i++){
          int v , p;
          cin >> v >> p;
          int par = ht(v , p);
          if(dis[v] < p){
               res.push_back(0);
               continue;
          }
          if(!check(v , par)) continue;
          int dist = dis[v] - dis[par];
          int l = -1 , r = vec[dist].size();
          while(r - l > 1){
               int mid = (l + r)/2;
               if(check(vec[dist][mid] , par)){
                    l = mid;
               }
               else if(st[par] > st[vec[dist][mid]])
                    l = mid;
               else if(ft[par] < ft[vec[dist][mid]])
                    r = mid;     
          } 
          int right = l;
          l = -1 , r = vec[dist].size();
          while(r - l > 1){
               int mid = (r + l)/2;
               if(check(vec[dist][mid] , par)){
                    r = mid;
               }
               else if(st[par] > st[vec[dist][mid]])
                    l = mid;
               else if(ft[par] < st[vec[dist][mid]])
                    r = mid;     
          }
               int left = r;
               res.push_back(right - left);
          //     er(right - left);
     }
}
void dfs(int u){
     st[u] = ++timer;
     mark[u] = true;
     for(auto v : adj[u]){
          if(!mark[v]){
               dis[v] = dis[u] + 1;
               dad[0][v] = u;
               for(int i = 1 ; i < lg ; i++){
                    dad[i][v] = dad[i-1][dad[i-1][v]];
               }
               vec[dis[v]].push_back(v);
               dfs(v);
          }
     }
     ft[u] = ++timer;
}

void graph(){
     cin >> n;
     lg = ceil(double(log2(n)));
     m = n - 1;
     for(int i = 1 ; i <= n ; i++){
          int v;
          cin >> v;
          adj[v].push_back(i);
     //     adj[i].push_back(v);
     }
     for(int i = 0 ; i < adj[0].size() ; i++)
          dfs(adj[0][i]);
     query();
}
int main(){
     ios;
     graph();
     for(auto w : res) cout << w << ' ';
     return 0;
}
Leave a Comment