解法の概要

辞書順最小が目的なので，先頭の項から順にできる限り値を小さくしていく貪欲法によりこの問題を解きます．

\(A(P)\) の \(i\) 番目の項を最小化する際には，「頂点 \(i\) に隣接するいずれかの頂点に \(x\) を書き込む必要がある」といった制約が基本的に課せられます．

\(1\) 項目から \(i\) 項目までの数列の辞書順最小化のための制約を守りながら \(i+1\) 項目を最小化することを繰り返すことによって，最終的に辞書順最小の数列を得ることができます．孤立点の取り扱いや，制約を守りながら \(i+1\) 項目を最小化する方法はやや複雑なので，以下に詳細を記します．

解法の詳細

はじめに以下の解説で使う用語の整理をします．

以下で用いる用語

• \(i\) 番目の操作で頂点 \(i\) と頂点 \(j\) を結ぶ辺が切られるとします．そのような頂点 \(j\) が既に定まっている場合頂点 \(i\) を確定した頂点，定まっていない場合頂点 \(i\) を 未定の頂点 と呼びます．更に，確定した頂点 \(i\) に対する頂点 \(j\) を，頂点 \(i\) のターゲット と呼びます．

• 頂点 \(i\) に隣接する頂点が \(2\) 個以上あり，いずれかの頂点 \(v\) に \(x\) を書き込む必要があるという制約があるとき，頂点 \(v\) に \(x\) が仮置きされている と呼びます．また頂点 \(i\) は頂点 \(v\) の 仮置き元であると呼びます．

解法

頂点 \(i\) が確定した頂点になる都度，実際に辺を切り，頂点 \(i\) のターゲット \(j\) に値を書き込みます．更に，頂点 \(i\) が確定したことで仮置きが無くなり得ることにも注意してください．

仮置きの制約を満たしながら，\(i\) 番目の項を最小化する方法を考えましょう．

\(A_i = 0\) にできるかの判定

既に頂点 \(i\) が孤立点である場合，\(A_i = 0\) とできます．そうでない場合，頂点 \(i\) の次数が \(2\) 以上ならば \(A_i = 0\) にできないことが示せます．（証明は後述）

頂点 \(i\) の次数が \(1\) の場合を考えます．頂点 \(i\) と結ばれた頂点を \(j\) とすると，\(A_i = 0\) とするためには，まず \(i > j\) を満たす必要があります．

何故ならば，\(i < j\) なら \(i-j\) 間の辺は頂点 \(i\) に対する操作をするときまで必ず残っているからです．同様にして，頂点 \(j\) は未定の頂点である必要があります．

逆に，\(j < i\) であり頂点 \(j\) が未定の頂点ならば，頂点 \(j\) のターゲットを \(i\) とすることで，\(A_i = 0\) にできます．

\(A_i =0 \) にできない場合

頂点 \(i\) に隣接する頂点 \(j\) 全てについて，頂点 \(j\) に仮置きされているまたは値が書き込まれているかを確認します．

1.仮置きまたは値が書き込まれているような隣接する頂点が存在しない場合

この場合，\(A_i\) を \(A\) の \(i-1\) 項目までに含まれる整数にすることはできません．なぜならば，\(i-1\) 項目までに含まれる整数は頂点 \(i\) に隣接しないいずれかの頂点に仮置きされている，もしくは値が書き込まれているからです．

そのため，\(A_i\) は \(A\) の \(i-1\) 項目までに含まない最小の正整数（これを \(x\) と置く）にするのが最適です．

頂点 \(i\) の次数が \(1\) の場合，頂点 \(i\) のターゲットは隣接する頂点 \(t\) に確定し，頂点 \(t\) に \(x\) が書き込まれます．

次数が \(2\) 以上の場合，頂点 \(i\) に隣接する各頂点に \(x\) を仮置きすればよいです．

2.仮置きまたは値が書き込まれているような隣接する頂点が存在する場合

そのような頂点のうち，（仮置きされている または 書き込まれている）値が最も小さいような頂点を選び，その頂点を \(t\) ，\(t\) に（仮置きされている または 書き込まれている）値を \(x\) とします．

このような頂点 \(t\) は，入力が木であることから（存在すれば）一意に定まります．

1 での議論と同様の議論により，\(A_i\) の最小値は \(x\) であることが分かります．頂点 \(i\) のターゲットを \(t\) とすればよいです．

このとき，頂点 \(t\) が仮置きされた状態である場合，頂点 \(t\) の仮置き元を \(s\) として，頂点 \(s\) のターゲットが \(t\) となり，頂点 \(s\) も確定した頂点になります．

コーナーケース1：確定の連鎖

\(i\) 項目の最小化により頂点 \(i\) が確定した頂点になった場合，頂点 \(i\) のターゲット \(j\) の次数が減少します．このとき，頂点 \(j\) が \(j < i\) を満たす未定の頂点であり，かつ次数が \(1\) になった場合に気を付ける必要があります．

仮置きが許されるのは，次数が \(2\) 以上の場合でした．孤立点でない場合必ず辺を切る必要があるため，次数が \(1\) になることで，頂点 \(j\) を確定した頂点にする必要があります．このような確定の連鎖に注意して下さい．

コーナーケース2：次数 \(2\) の特殊なケース

\(A_i = 0\) にできない場合の 2. では，（仮置きされている または 書き込まれている）値が最も小さいような頂点を選ぶと述べました．しかし実際には，頂点 \(i\) に隣接する頂点 \(j\) であって，\(j < i\) を満たし，かつ頂点 \(j\) が未定の頂点で次数が \(2\) であるものは 2. の候補に入れてはいけません．

何故ならば，頂点 \(j\) の仮置き元を \(k\) ，仮置かれている値を \(x\) とすると，\(j\) に \(x\) を書き込むことで \(A_k = A_i = x\) を達成できそうですが，実際には \(k-j\) の辺を切ることで \(j\) の次数が \(1\) となり，\(j\) のターゲットが \(i\) に確定して \(j-i\) の辺が \(i\) に対する操作の前に切られてしまい，\(A_i=x\) が達成不可能になるからです．

まとめ

これらのコーナーケースに気を付けながら，\(i=1,2,\ldots,N\) の順に \(A_i\) の最小化を行うことで，辞書順最小の \(A\) が得られます．

以上の処理は全て \(\mathrm{O}(N\log N)\) で実装できます．

---

【頂点 \(i\) の次数が \(2\) 以上ならば \(A_i = 0\) にできないことの証明】

頂点 \(i\) への処理を行う際に \(2\) 種類以上の値が仮置きされていることはないため，次数が \(2\) 以上の場合は確定した頂点，または \(i\) よりも頂点番号が大きい頂点が \(1\) 個以上隣接しています．そのため，頂点 \(i\) の次数が \(2\) 以上の場合，\(A_i = 0\) とすることはできません．