ABC202 E Count Descendants
あらかじめ, 各頂点について根からの距離($ distとおく), 初めてその頂点にたどり着いた時間($ inとおく), 最後にその頂点にたどり着いた時間($ outとおく)を前計算しておく. そして, $ dist_j = iなる$ jについて, 数列$ A_iに$ in_jを追加し, さらに昇順にソートしておく.
ここで, 次の性質を用いる(1.は自明, 2.の証明は解説参照).
1. $ uから根への最短パス上に頂点$ U_iが存在する $ \Leftrightarrow 根から$ uへの最短パス上に頂点$ U_iが存在する
2. 根から$ uへの最短パス上に頂点$ U_iが存在する $ \Leftrightarrow $ in_{U_i} \leq in_u \leq out_{U_i}
1, 2より, $ uから根への最短パス上に頂点$ U_iが存在することは, $ in_{U_i} \leq in_u \leq out_{U_i}であることと同値である.
これを踏まえると, $ A_{D_i}について, $ in_{U_i}以上$ out_{U_i}以下の要素が何個あるか求めればよく, これは二分探索を用いて各クエリごとに$ O(\log N)で求められる.
よってこの問題を$ O((N + Q) \log N)で解くことができた.