AtCoder Beginner Contest 202E

ABC202E

Euler tour, sub tree, DFS. 取りあえず，木に関するクエリ問題なので， 少ない回数の DFS で多くのクエリの処理を同時に行いたい．
頂点 \(u\) 以下の部分木で，深さが \(d\) である頂点の個数がクエリ毎の答え． これは，深さ \(d\) となる頂点全体から，\(u\) の部分木に含まれる部分を抽出すればよい． あるいは，共通部分を取り出すと言っても良い． これは Euler tour で実装可能．Euler tour は部分木を区間で扱う方法である．

DFS をしたとき，頂点\(v\) に入ったとき，出るときに in(v), out(v) を更新する． DFSをしているときの行きがけ順で頂点に番号を振ると， \(v\) 以下の部分木に現れる頂点はすべて in(v) 以上 out(v) 以下となる．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll n,m; cin >> n ; m = n-1;

  vvll to(n);

  rep1(i,m){ // rem : rep1

    ll p ; cin >> p;

    p--;

    to[i].push_back(p);

    to[p].push_back(i);

  }

  vll id(n,-1);

  vll l(n, INFL), r(n, -INFL);

  vvll v(n);

  ll i = 0;

  auto dfs = [&](auto f, ll cu, ll pa = -1, ll d = 0) -> pll {

   

    id[cu] = i;

    v[d].push_back(i);

    chmin(l[i], i);

    chmax(r[i], i);

    for(auto ne: to[cu]) if(ne != pa){

      i++;

      auto [nl,nr] = f(f, ne, cu, d+1);

      chmax(r[id[cu]], nr);

    }

    return pll(l[id[cu]], r[id[cu]]);

  };

  dfs(dfs, 0);

  ll q; cin >> q;

  rep(qi,q){

    ll u,d; cin >> u >> d;

    u--;

    auto itl = lower_bound(all(v[d]), l[id[u]]);

    auto itr = upper_bound(all(v[d]), r[id[u]]);

    cout << itr-itl << endl;

  }

  return 0;

}