oliverx3の精進記録

ABC202 E - Count Descendants

オイラーツアー賢すぎ！色々な解法があるっぽい

問題概要

$N$ 頂点からなる根付き木が与えられる。クエリ $(u, d)$ をたくさん処理せよ。

クエリ $(u, d)$ : $u$ を根とする部分木で頂点 $1$ からの深さが $d$ のものは何個あるか。

$2 \leq N \leq 2 \times 10^5$

$1 \leq Q \leq 2 \times 10^5$

解説

部分木を扱う典型テクとして、オイラーツアーというものがある。木をいい感じの列に変換するテク。

まず根から DFS をする。カウンター $k$ を持っておく。

頂点 $i$ を訪れたら $\mathrm{in}[i]$ に $k$ を記録し、 $k$ をインクリメント。（行きがけ順に番号をつける）

頂点 $i$ の部分木を全て探索したら、 $\mathrm{out}[i]$ に $k$ を記録する。（帰りがけ順に番号をつける）

このとき、木をオイラーツアーを用いて変換した列 $\mathrm{in}$ は嬉しい性質を持っている。頂点 $i$ の部分木の頂点集合は列の $[\mathrm{in}[i], \mathrm{out}[i])$ で表される。

木に対しては使えなかったさまざまなアルゴリズムやデータ構造が、木を列に変換したことで使えるようになって、嬉しい。

この問題においてもオイラーツアーが使える。

二次元配列 $\mathrm{ls}$ において、 $\mathrm{ls}[dep]$ に深さが $dep$ である頂点の $\mathrm{in}$ の値を入れておく。それぞれのクエリごとに、 $\mathrm{ls}[d]$ 内の $\mathrm{in}[u] \leq x \lt \mathrm{out}[u]$ なる $x$ の個数を数えればよくて、これは二分探索で高速にできる。よって $O(N \log N + Q \log N)$ で解けた。

反省点

オイラーツアー、名前とやりたいことは知っていたが、実際の問題でどうやって使うのかやどうやって実装するかをあまり詳しく知らなかった。オイラーツアーをした後の問題でにぶたんを使うことは超典型なので、すぐにできるようにしたい。

提出コード

クエリが先に与えられてるので、他にもいろいろな解法があるっぽい。解説放送にあったマージテクが賢そうだった。