AtCoder Regular Contest 142 C問題 Tree Queries

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

インタラクティブ問題
$N$ 頂点からなる木 $T$ がある. 以下の質問を高々 $2N$ 回することにより, $\operatorname{dist}_T(1,2)$ を求めよ.

$u+v \gt 3$ となる $1 \leq u,v \leq N$ に対して, $\operatorname{dist}_T(u,v)$ を尋ねる.

制約

$3 \leq N \leq 100$
$T$ は最初に決定される.

解法

定理1

グラフ $G=(V,E)$ に対して, $u,v \in V$ で $uv \not \in E$ ならば,

$\displaystyle \operatorname{dist}_G(u,v)=\min_{\substack{w \in V \\ w \neq u,v}} (\operatorname{dist}_G(u,w)+\operatorname{dist}_G(w,v))$

である.

この定理1を利用して $\operatorname{dist}_T(1,2)$ を求めることにする. $2(N-2)$ 回分を使って,

$\operatorname{dist}_T(1,v)~(v=3, \dots, N)$
$\operatorname{dist}_T(2,v)=\operatorname{dist}_T(v,2)~(v=3, \dots, N)$

を尋ねる.

このとき,

$\displaystyle X:=\min_{\substack{3 \leq w \leq N}} (\operatorname{dist}_T(1,w)+\operatorname{dist}_T(w,2))$

を解答として使いたいが, そのまま解答にしてしまうと不正解になってしまう場合がある. これは定理1 が辺 $1,2$ が存在しないことを仮定しているからである.

そこで, 辺 $1,2$ がある場合に $X$ がどのような値になるかを観察する. 実は, この場合, $N \geq 3$ で $T$ は木なので, 必ず $X=3$ となる. よって, この対偶を取って, $X \neq 3$ ならば, 辺 $1,2$ は $T$ に存在しないことになる. これで $X \neq 3$ の場合は $\operatorname{dist}_T(1,2)=X$ であることがわかった.

よって, $X=3$ の場合を考えることになる. このとき, $\operatorname{dist}_T(1,2)$ の候補は $1$ または $3$ である. 今, $T$ は木なので, 以下が従う.

定理2

木 $T=(V,E)$ において, $u,v \in V$ は $u \neq v$ であるとする. このとき, $\operatorname{dist}_T(u,v)=\operatorname{dist}_T(u,w)+\operatorname{dist}_T(w,v), w \neq u,v$ を満たす $w \in V$ はちょうど $(\operatorname{dist}(u,v)-1)$ 個である.

$X=3$ という仮定のもとで, もし, $3=\operatorname{dist}_T(1,w)+\operatorname{dist}_T(w,2)$ となる頂点 $w~(w \neq 1,2)$ の個数がちょうど $2$ 個ではなかったとすると, 定理2から $\operatorname{dist}_T(1,2) \neq 3$ であるから, $\operatorname{dist}_T(1,2)=1$ である.

$X=3$ かつ $3=\operatorname{dist}_T(1,w)+\operatorname{dist}_T(w,2)$ であるような頂点 $w~(w \neq 1,2)$ の個数がちょうど $2$ 個のとき, その2つの頂点を $x,y$ とする. このとき, $x,y$ は $X=3$ であるから, 頂点 $1$ または頂点 $2$ のうちどちらか一方のみと隣接している.

$x,y$ が共に頂点 $1$ と隣接している (または共に頂点 $2$ に隣接している場合): $\operatorname{dist}_T(x,y)=2$ である. また, この場合, $\operatorname{dist}_T(2,x)=2$ なので, 頂点 $2$ と頂点 $x$ には共通の近傍 $z$ が存在する. $z \neq 1$ 仮定すると, $\operatorname{dist}_T(1,z)=2, \operatorname{dist}_T(2,z)=1$ であり, $x,y$ の名付け方から, $y=z$ でなくてはならない. しかし, これだと木に $2,z,x$ を頂点とするサイクルが存在することになり矛盾する. よって, $z=1$ であるから, 辺 $1,2$ が存在する.
の一方は頂点と隣接し, 他方は頂点と隣接している場合: 対称性から, 頂点は頂点と, 頂点は頂点と隣接しているとする. このとき, には辺と辺が存在する. このとき, である.
- 辺 $1,2$ が存在するならば, $x,1,2,y$ は $x,y$ パスとなり, $T$ は木なので, $\operatorname{dist}_T(x,y)=3$ である.
- 辺 $1,2$ が存在しない場合. もし, 辺 $x,y$ が存在しないと仮定すると, 辺 $1,2$ と辺 $x,y$ は存在しないので, 頂点 $2$ , 頂点 $x$ とは異なる新たな頂点 $z$ で $z$ が頂点 $1$ と頂点 $y$ の共通近傍になるようなものが存在する. しかし, 辺 $1,y$ が存在しないことに注意すると, $\operatorname{dist}_T(1,z)+\operatorname{dist}_T(z,2)=1+2=3$ でとなるが, これは $3=\operatorname{dist}_T(1,w)+\operatorname{dist}_T(w,2)$ であるような頂点 $w~(w \neq 1,2)$ の個数がちょうど $2$ 個であり, それを $x,y$ と名付けたことに矛盾する. 従って, 辺 $x,y$ が存在するので, $\operatorname{dist}_T(x,y)=1$ である.

従って, 転換法を利用することにより,

$\operatorname{dist}_T(x,y)=2 \Rightarrow$ 辺 $1,2$ が存在する $\Rightarrow \operatorname{dist}_T(1,2)=1$ である.
$\operatorname{dist}_T(x,y)=3 \Rightarrow$ 辺 $1,2$ が存在する $\Rightarrow \operatorname{dist}_T(1,2)=1$ である.
$\operatorname{dist}_T(x,y)=1 \Rightarrow$ 辺 $1,2$ が存在しない $\Rightarrow \operatorname{dist}_T(1,2) \neq 1 \Rightarrow \operatorname{dist}_T(u,v)=3$ である.

と結論づけることができる. よって, $\operatorname{dist}_T(x,y)$ を尋ねることによって $\operatorname{dist}_T(1,2)$ を特定できる.

以上から, 高々 $2(N-2)+1=2N-3$ 回で $\operatorname{dist}_T(1,2)$ を特定できた.

解法の概略

$3 \leq v \leq N$ それぞれに対して, $\operatorname{dist}_T(1,v), \operatorname{dist}_T(2,v)$ を尋ねる.
$\displaystyle X:=\min_{3 \leq w \leq N} (\operatorname{dist}_T(1,w)+\operatorname{dist}_T(w,2))$ としたとき, $X \neq 3$ ならば $\operatorname{dist}_T(1,2)=X$ である.
$X=3$ のとき, $X=\operatorname{dist}_T(1,w)+\operatorname{dist}_T(w,2)$ となる頂点 $w~(3 \leq w \leq N)$ の個数がちょうど2個でなければ, $\operatorname{dist}_T(1,2)=1$ である.
$X=3$ かつ $X=\operatorname{dist}_T(1,w)+\operatorname{dist}_T(w,2)$ となる頂点 $w~(3 \leq w \leq N)$ の個数がちょうど2個のとき, その2個の頂点を $x,y$ としたとき, $\operatorname{dist}_T(x,y)$ を訪ね, $\operatorname{dist}_T(x,y)=1$ ならば $\operatorname{dist}_T(1,2)=X=3$ , そうでなければ, $\operatorname{dist}_T(1,2)=1$ である.