geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

AtCoder Beginner Contest 267 F - Exactly K Steps

ABC 木全方位木DP Link-Cut Tree

最遠点を求めた後にLink-Cut Treeで $K$ 回移動する解法で解いてみました。

ここでは、Link-Cut Treeの詳細な説明は割愛し、必要な部分だけを記載します。

詳細は以下のサイトを見るのが良いと思います。

Link-Cut Treeの実装メモ - 日々ｄｒｄｒする人のメモ

Link-Cut 木 - ei1333の日記

Link-Cut木では、以下のような操作ができます。

$evert(v)$ :頂点 $v$ を根にする
$expose(v)$ :根から頂点 $v$ までのパスをHeavy-edgeで繋ぐ(パス上の頂点から出るその他の辺は全てLight-edgeになる)

頂点 $s$ を根とし、頂点 $t$ までのパスをHeavy-edgeで繋ぐと、 $s-t$ 間に含まれる全ての頂点が同一の平衡二分探索木によって管理されます。

この平衡二分探索木の頂点を通りがけ(in-order)順に並べると $s-t$ 間のパス順になるようになっています。

続いて、平衡二分探索木を通りがけ順に並べた時の $k$ 番目の頂点を高速に得る方法を考えます。

まず、平衡二分探索木に部分木のサイズを持たせます。すると、通りがけ順で $X$ 番目となる頂点が、今いる頂点 $v$ の左部分木か、右部分木か、 $v$ 自身かというのが、以下の場合分けで判定できます。なお、1-indexedで並べるものとします。

$S$ =頂点 $v$ の左部分木のサイズ+1
とします。+1は頂点 $v$ の分です。

$X = S$ の場合
通りがけ順では、左部分木を全て並べた後、頂点 $v$ を並べます。
左部分木の $X-1$ の頂点を並べた後に、 $X$ 番目として $v$ を並べるので、このケースでは $v$ を返せば良いです。
$X \lt S$ の場合
左部分木に $X$ 番目が存在するので、 $v$ の左の子の $X$ 番目を調べます。
$X \gt S$ の場合
右部分木に $X$ 番目が存在するので、 $v$ の右の子について、 $S$ 個の頂点を除いた $X-S$ 番目を調べます。

このように根から順に二分探索のような感じで調べていくことで $X$ 番目の頂点を得ることが可能です。

計算量は、平衡二分探索木の高さ分の探索をするので、平衡二分探索木であることを考えると、ならしlog時間くらいになると思われます。

以上から、元の問題を以下のように解くことができます。

頂点 $i$ からの最遠点 $V_i$ を、すべての頂点について求める

各クエリで与えられるの頂点 $U_i$ をLink-Cut Treeの根とし、最遠点 $V_{U_i}$ を根と繋ぐ

$U_i$ から $V_{U_i}$ までのパス上における $K_i$ 番目の頂点をLink-Cut Treeの平衡二分探索木から求める

計算量を考えます。
最遠点は、全方位木DPにより求めたので、 $O(N)$ です。
Link-Cut Treeで行う各処理は、 $O(logN)$ で処理できると思うので、 $O(QlogN)$ です(おそらく)。
よって、全体で $O(N+QlogN)$ だと思います。

提出コード:Submission #34979495 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)

Link-Cut Treeにはモノイドを乗せるようにしてあるので、構造体等が定義されていますが、この問題を解くにあたっては不要です。