ARC142-C Tree Queries (too small)

「 $N = 4$ のケースで困った」と言う意見をいくつか見たので、そう言った時の対処法（荒療治）を紹介します
以下では木 $T$ の頂点 $u,v$ の距離を $d_T(u,v)$ と書くことにします

解法1

$\mathcal{T}$ を $N$ 頂点ラベル付き木全体の集合とします
これはケイリーの定理より全部で $N^{N-2}$ 個あり、例えばこちらの記事の証明 1 を参考にしてそれなりに効率的に全列挙することが出来ます

$\mathcal{S} \subseteq \mathcal{T}$ に対し、 $dp[\mathcal{S}]$ を「木の候補が $\mathcal{S}$ である時、残り必要な最低質問回数」とします
「木の候補が $\mathcal{S}$ である時、（回答に応じて行動を変えることで）どのような回答に対しても高々 $dp[\mathcal{S}]$ 回の質問で答えを当てられる」戦略が存在し、「どんな場合に対しても $dp[\mathcal{S}]$ より少ない回数の質問で答えを当てられる」ような戦略は存在しないと言うことです

$| \{ d_T(1,2) \mid T\in \mathcal{S} \} | = 1$ である時、明らかに $dp[ \mathcal{S} ]=0$ です
そうで無い時は「最悪の答えが返ってきた時の結果が最良であるような質問をする」ことを考えると、
$dp [ \mathcal{S} ] = \min_{u,v} \max_{ k \in \mathbb{Z} } dp [ \mathcal{S}_{u,v;k} ]$
が成り立ちます（ただし $\mathcal{S}_{u,v;k} = \{ T \in \mathcal{S} \mid d_T(u,v)=k \}$ ）

この dp 配列を全て計算しておき適切に質問を繰り返すことで、必ず高々 $dp[\mathcal{T}]$ 回の質問で答えを出力することが出来ます
当然 $dp[\mathcal{T}]$ は $2N-1$ 以下である（そうでなければ問題が問題として成立しない）ことから、この解法の正当性が示されます

dp 配列の大きさ（key の個数）は $2^{ |\mathcal{T}| } = 2^{N^{N-2}}$ であり、これは $N=4$ の時に $2^{16}$ , $N=5$ の時に $2^{125}$ なので、 $N\leq 4$ の時のみ使える解法になります

解法2

質問の種類は $\binom{N}{2} -1$ 通りしかありません
もしこれらの質問を全て聞けたのならば、後に述べるように答えは簡単に求まります
従って、 $\binom{N}{2} -1 \leq 2N$ の時のみ全部の質問をしてしまうと言う解法を用いることで、 $N\leq 5$ の時は解くことが出来ます

最後に質問を全て聞けた時の解法例を書いておきます
木の辺候補は回答が $1$ であるような頂点対のみなので、そのような頂点対の個数が $N-1$ であれば実際に木を作って見ればよく、 $N-2$ であれば $1,2$ を結ぶ辺が存在することになるので、 $1$ が答えになります

その他（上とは完全に別件）

テストケースが弱くて $N=4,5$ くらいでも落ちるケースが存在するコードが AC になっていると言う話があったはずです
AC しても必ずしもコードが正しいとは限らないので、upsolve をする人は手元でチェックコードを回すと良いかもしれません（ $N \leq 8$ のラベル付き木全部に対して正しく動いているかなどは簡単に確かめられると思います）
逆に問題/テストケースを作る人は、 $\sum N \leq 10^5$ などのマルチテスト問題にすると、一つのテストケース内に $N$ が小さい場合を全部詰め込めて良いと言う話も出ており、確かに〜となりました

blogskol

思わず声に出して読みたくなるブログ

ARC142-C Tree Queries (too small)

解法1

解法2

その他（上とは完全に別件）