AGC 012 B - Splatter Painting

• 問題
• AC

クエリを逆順に処理し、頂点の色が最初に塗った色に固定される問題に変える。頂点$v$から処理した最大の深さを$\operatorname{depth}[v]$、頂点$v$に塗った色を$\operatorname{color[v]}$（どちらも初期値$0$）として、クエリ毎にDFSで更新していく。$\operatorname{depth}[v]$以下の深さの更新は影響しないので、枝刈りしてよい。

各頂点$v$について$\operatorname{depth}[v]$の更新は最大で$\max d_i$回しか起こらず、したがって$v$の隣接頂点が走査される回数も高々$\max d_i$回である。クエリをすべて処理した時、前者の合計は${\mathcal O}(N\max d_i)$で後者の合計は${\mathcal O}(M\max d_i)$なので、計算量は${\mathcal O}(Q+(N+M)\max d_i)$である。

---

隣接頂点が走査される回数がなぜか${\mathcal O}(|V|^2)$な気がして困っていた。

ABC 132 E - Hopscotch Addictで失敗した記憶が頭にあったせいかも。いちおう整理しておくと、$N(x):=\{(u, v) \in V^2 \:|\: uとvの最短距離がx\}$とするとき、当然$|N(1)| = {\mathcal O}(|E|)$であるが、$N(2), N(3), ...$の大きさは${\mathcal O}(|E|)$とは限らず¹、一般に${\mathcal O}(|V|^2)$である。

---

1. 例えばスターグラフは$|E|= \Theta(|V|)$だが$N(2) = \Theta(|V|^2)$になる。 ↩︎