CodeChef - Path containing K Nodes

• 問題
• AC

$u$が$v$の先祖かどうか調べる方法を思い出す:

• 各頂点$v$にDFS順序で行きの番号$\operatorname{pre}[v]$と帰りの番号$\operatorname{post}[v]$を振る。$u$が$v$の（広義の）先祖である必要十分条件は$\operatorname{pre}[u] \le \operatorname{pre}[v]$かつ$\operatorname{post}[v] \le \operatorname{post}[u]$が成り立つことである。

$K$個の頂点のうち、$\operatorname{pre}[u]$が最大であるような$u$と$\operatorname{post}[v]$が最小であるような$v$を選ぶ。この二つが同一のとき、上の性質を考えると$K$個の頂点はすべて$u=v$の先祖なので、一つのパス上にある。

$u \neq v$の場合を考える。パスが存在するならこの2点が（極小のパスの）端点になっているので、$K$個の頂点が$u$または$v$の先祖であり、かつ$u, v$のLCAの（狭義の）先祖ではないことが必要十分条件である。