[1] 解の構築

類似度が \(1\) であるような順列を常に構築できます。はじめに構築するアルゴリズムを示し、次にアルゴリズムの出力する順列の類似度が \(1\) になっていることを示します。

アルゴリズム

Step0. 長さ \(N\) の数列 \(P\) を用意する。この時点ではどの値も未定である。

Step1. 木の葉の頂点を全て queue に入れる。

Step2. queue に入っている頂点が \(2\) 個以上ある限り、以下を繰り返す。

• queue の頂点を \(2\) 個取り出す（取り出した頂点を \(u,v\) とする）。 \(P_u= v, P_v=u\) とする。さらに、木 \(T\) から頂点 \(u,v\) を取り除き、新たに葉になった頂点があればその頂点を queue に入れる。

Step3. \(N\) が奇数のときに限り、Step2 の終了後、queue には \(1\) 個の頂点 \(x\) が入っている。 \(P_x=x\) とする。

正当性の証明

はじめに、\(1,2,\ldots,N\) について上のアルゴリズムではちょうど \(1\) 度 \(P\) に割り当てられていることから、 \(P\) は確かに順列であることが確認できます。

次に、\(P\) の類似度が \(1\) であることを数学的帰納法を用いて示します。

\(N=1,2\) のとき、上のアルゴリズムが構築する順列の類似度は \(1\) です。

\(N\geq 3 \) のときを考えます。 Step2 ではじめて取り出した二つの頂点を \(a,b\) とします。割り当て方から、どのようなパスにおいても最長共通部分列に \(a,b\) がともに含まれることはありません。共通部分列に \(a\) が含まれる場合、割り当て方からそのような共通部分列の長さは \(1\) になります。 \(b\) についても同様です。

このことから、サイズが \(2\) 小さい問題になります。これを繰り返すことで証明が完了します。

---

[2] 実装例

Python:（実装では queue の代わりに stack を使用しています）

n = int(input())
g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
deg, p = [0] * n, [0] * n
st = []
for i in range(n):
    deg[i] = len(g[i])
    if deg[i] == 1:
        st.append(i)
while len(st) >= 2:
    u = st.pop()
    v = st.pop()
    p[u], p[v] = v, u
    for to in g[u]:
        deg[to] -= 1
        if deg[to] == 1:
            st.append(to)
    for to in g[v]:
        deg[to] -= 1
        if deg[to] == 1:
            st.append(to)
if len(st):
    x = st.pop()
    p[x] = x
p = [v + 1 for v in p]
print(*p)

---

[3] おまけ

\(\mathrm{O}(N^2)\) で動作するジャッジコードを考えて下さい。（ABC-E,F 程度？）