Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 267 F問題 Exactly K Steps

AtCoder ABC267 ABC F問題 500 pts

問題

提出解答

問題の概要

$N$ 頂点の木 $T=(V,E)$ が与えられる. ただし,

$V:=\{1,2,\dots,N\}$
$E:=\{A_j B_j \mid j=1,2, \dots, N-1\}$

次の $Q$ 個の問に答えよ.

問 $q$ : 頂点 $U_q$ からの距離が $K_q$ である頂点は存在するか? また, 存在するならばそのような頂点の例を1つ挙げよ.

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq A_j \lt B_j \leq N$
$1 \leq Q \leq 2 \times 10^5$
$1 \leq U_q, K_q \leq N$
$T$ は木.

解法

木 $T$ 上の2頂点 $u,v$ 間の距離を $\operatorname{dist}(u,v)$ と書くことにする.

木 $T$ の直径の両端をなす2頂点を $x,y$ とする. このとき, 任意の頂点 $u,v \in V$ に対して, $\operatorname{dist}(u,v) \leq \max (\operatorname{dist}(u,x), \operatorname{dist}(u,y))$ が成り立つ. よって, 次の問題に帰着できる.

頂点 $u$ に対して, 次のうち, 少なくとも一方を満たすような頂点 $v$ は存在するか? するならばその頂点の例を挙げよ. なお, $T$ において, 頂点 $u$ の $x,y$ を根とした根付き木における深さを $\operatorname{depth}_x(u), \operatorname{depth}_y(u)$ と書く.

$\operatorname{depth}_x(u) \leq k$ であり, $v$ は頂点 $x$ を根とする根付き木において $u$ は $v$ の先祖で, $\operatorname{depth}_x(v)=\operatorname{depth}_x(u)-k$ である.
$\operatorname{depth}_y(u) \leq k$ であり, $v$ は頂点 $y$ を根とする根付き木において $u$ は $v$ の先祖で, $\operatorname{depth}_y(v)=\operatorname{depth}_y(u)-k$ である.

上と下の問題はそれぞれ根を固定した Level Ancestor Problem であり, クエリ先読み, DFS を利用することによって, $O(N+Q)$ 時間で解くことができる.