頂点 \(1\) から頂点 \(N\) の距離と、頂点数の偶奇が一致しない場合は明らかに、よい手順は存在しません。 実は、そうでない場合には常によい手順が構成可能です。 また、よい手順が実現可能であるとき、任意のよい手順において必ず駒が置かれる頂点の集合が存在し、 さらにそれ以外の頂点で駒を置く必要がある頂点の候補は限られます。

以下、具体的な構成方法を記述します。 これ以降、木上で \(2\) 頂点 \(u,v\) を結ぶパスを \(\mathrm{path}(u,v)\) 、その長さを \(d(u,v)\) とします。 まず、\(\mathrm{path}(1,N)\) 上の点は明らかに、必ず駒が置かれる必要があります。 \(\mathrm{path}(1,N)\) 上の辺を切断し、\(\mathrm{path}(1,N)\) 上の頂点を根とした部分木の集合を考えたとき、 各頂点 \(i\) が子孫として持つ部分木のサイズ（その頂点自身も含む）を \(w_i\) と置きます。

ここで、「ある頂点 \(s\) に対して、\(s\) より子孫側には駒を移動させなくてよい」と仮定します。 すると、駒の位置と \(s\) との距離の増減に着目し、各頂点を選んだ時に駒が \(s\) に近づく操作となるか、遠ざかる操作となりうるかを考えると、\(s\) の部分木内の頂点を選んだ操作では必ず駒は \(s\) に近づき、それ以外の頂点を選んだ操作では \(s\) から遠ざかる可能性があることより、

\(d(1,s)+(N-w_s)\geq d(N,s)+w_s\) ーⒶ

が成り立つ必要があります。

これに違反する頂点が存在する場合、このような頂点は、\(1\) つのパスをなします（Ⓑ：証明は後述）。

この場合、パスの最も子孫側の頂点を \(t\) とします。 \(t\) の子のいくつかを選び、その部分木のサイズの総和を \(W\) とします。 \(W\) と \(w_t-W\) 個の頂点を、まず駒を \(t\) に近づけるために使い、他の頂点とペアにして消費していきます。 仮定より、\(t\) の部分木内の頂点が余りますが、このとき \(W\) 個のうちの余りが \(w_t-W\) 個のうちの余り以上であれば、 「選んだ子のうち \(1\) つに移動させる→\(t\) に戻す」という形でペアとして消化していくことが可能です。 また、\(W\) の中の \(1\) つの部分木が余りの過半数を占めてしまうとこれが出来なくなりますが、\(t\) の子 \(p\) はⒶに違反しないことから、これを避けることは必ず可能です。

したがって、\(t\) の子から出来るだけ少ない頂点を選び、選んだ子の部分木のサイズの総和 \(W\) が

\(W\geq (w_t-W)-(d(1,t)+(N-w_t)-d(N,t))\)

\(\iff\) \(2W\geq w_t-(d(1,t)+(N-w_t)-d(N,t))\)

を満たすようにすればよいです。

また、Ⓐに違反する頂点が存在しない場合、\(\mathrm{path}(1,N)\) 上の頂点のみを経由する手順が構築可能です。方法を以下に記します。

\(\mathrm{path}(1,N)\) 上の点を \(1\) つ取り、\(s\) とします。 \(1\) から \(s\) までのパス上のうち \(s\) 以外の点 \(i\) に対する \(w_i\) の総和を \(B_s\)、 \(s\) から \(N\) までのパス上のうち \(s\) 以外の点 \(i\) に対する \(w_i\) の総和を \(F_s\) とします。\(w_s, B_s+d(1,s), F_s-d(N,s)\) のうちどの値もこれらの総和の半分を越えない時、この頂点 \(s\) を中心としてそれぞれの頂点群からペアで消費することにより、\(1\) から \(N\) に至るパス上のみを経由するよい手順を構築可能です。

そして、Ⓐに違反する頂点が存在しない場合、\(\mathrm{path}(1,N)\) 上で、上記の条件を満たす点が必ず存在します（Ⓒ：証明は後述）。

---

■Ⓑの証明

Ⓐに違反する頂点の親もⒶに違反することは明らかです。 祖先と子孫の関係にない異なる 2 頂点 \(i,j\) がともにⒶに違反すると仮定して矛盾を導きます。

このとき、\(i\) に関して

\(d(1,i)-d(N,i)+(N-w_i)<w_i \) \(\iff \) \(d(1,i)-d(N,i)+(N-w_i)+1\leq w_i\)

が成り立ちます。 ここで、\(d(1,i)-d(N,i)\geq -d(1,N)\) であることを用いると、

\((N-w_i)-d(1,N)+1\leq w_i\) （等号成立の可能性があるのは \(i\) が \(1\) の部分木内のとき）

ですが、 \((N-w_i)-d(1,N)\) は \(w_i\) の部分木と \(\mathrm{path}(1,N)\) 上の頂点を除いた頂点の総数以上です。\(j\) は、\(i\) の部分木内にはないため、\(j\) の部分木は \(i\) の部分木とは重複を持たないはずで、

\(w_j\leq (N-w_i)-d(1,N)+1\) （等号成立の可能性があるのは \(j\) が \(\mathrm{path}(1,N)\) 上の時）

が成立します。以上より \(w_j\leq w_i\) で、等号が成立するのは \(i\) が \(1\) の部分木内、\(j\) が \(\mathrm{path}(1,N)\) 上であるときに限ります。

したがって、\(w_j\leq w_i\) かつ \(w_i\leq w_j\) ですが、双方の等号成立には \(i=j=1\) が必要で、矛盾が導かれます。

---

■Ⓒの証明

\(s\) を \(\mathrm{path}(1,N)\) 上で \(1\) から順に動かします。仮定より、 \(w_s\) が過半数にはなりません。

定義より、\(s=1\) で \(B_s+d(1,s)=0\) 、\(s=N\) で \(F_s-d(N,s) =0\) です。どちらかが条件を満たす場合は考えなくてよいので、\(s=1\) では \(F_s-d(N,s)\) が過半数、\(s=N\) では \(B_s+d(1,s)\) が過半数と仮定します。\(s\) より \(1\) つ \(N\) に寄った頂点を \(t\) として、 \(s\) では \(F_s-d(N,s)\) が過半数かつ、\(t\) では \(F_t-d(N,t)\) が過半数でないような頂点 \(s,t\) が存在します。

このとき、

\(F_t-d(N,t) = (F_s-w_t)-(d(N,s)-1) = F_s-d(N,s) -w_t+1\)

\(B_t+d(1,t) = (B_s+w_s)+(d(1,s)+1) = B_s+d(1,s) +w_s+1\)

より、

\(F_s-d(N,s) > B_s+d(1,s) +w_s\) \(\iff\) \(F_s-d(N,s) -w_t+1+w_t > B_s+d(1,s) +w_s+1\)

\(\iff\) \(F_t-d(N,t)+w_t > B_t+d(1,t)\)

したがって、\(B_t+d(1,t)\) は過半数でなく、仮定より \(F_t-d(N,t)\) と \(w_t\) も過半数でないので、 \(t\) は条件を満たします。