コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1638 (記事作成時点)
供養
解法1
- 根からEuler Tourをしたときの経路を $S = \dots, v_{i}, \dots, v_{i}, \dots$、$v_{i}$ に最初に訪れた順番と最後に訪れた順番をそれぞれ $v_{i}^{\mathrm{in}}, v_{i}^{\mathrm{out}}$ とすると、$v_{i}$ の子孫はすべて $v_{i}^{\mathrm{in}}$ 番目から $v_{i}^{\mathrm{out}}$ 番目の間に登場する
- 各点について深さごとに $v_{i}^{\mathrm{in}}$ を昇順に持つ配列を $E$ とすると、各 $U_{j}, D_{j}$ について、$E_{D_{j}}$ のうち $v_{U_{j}}^{\mathrm{in}}$ から $v_{U_{j}}^{\mathrm{out}}$ の間に登場した点数がクエリの解となる
実装
計算量は $O(Q\mathrm{log}N)$
公式解説
嘘解法
- 各点 $u$ について、$u$ からちょうど距離 $2^{k}$ にある子孫の集合を $\mathit{Dec}_{u, k}$ で持っているとする
- 以下のように関数 $F(u, d)$ を定義する
- $d \lt 0$ のとき $0$ を返す
- $d = 0$ のとき $1$ を返す
- $2^{k} \le d$ である最大の $k$ について、
- $2^{k} = d$ ならば $\mathit{Dec}_{u, k}$ の長さを返す
- $2^{k} \lt d$ ならば $\sum_{v \in \mathit{Dec}_{u, k}} F(v, d - 2^{k})$ を返す
- 各点の深さを $d_{i}$ としたとき、各 $U_{j}, D_{j}$ について $F(U_{j}, D_{j} - d_{U_{j}})$ を返す
実装
計算量は $O(NQ)$
- 全ての足の長さが3のSpider Graphで、$(U_{j}, D_{j})= (1, 3)$ というクエリを投げると1回で $O(N)$ になる
- そのような最悪Caseがないのか問題としては通る
躓いた点
- 嘘解法で解こうとした
- 時間内に実装が間に合わなかった
