[1] Constructing a solution

You can always construct a permutation with the similarity of \(1\). We will first present an algorithm to construct it and then show that its similarity is \(1\).

Algorithm

Step 0. Prepare a sequence \(P\) of length \(N\) whose elements are undecided.

Step 1. Insert all leaves of the tree into a queue.

Step 2. Repeat the following as long as the queue has two or more vertices.

• Remove two vertices from the queue (let \(u\) and \(v\) be the removed vertices). Let \(P_u= v\) and \(P_v=u\). Remove the vertices \(u\) and \(v\) from the tree \(T\). If there are leaves after this removal, put all of them into the queue.

Step 3. After Step 2, the queue contains one vertex \(x\) only if \(N\) is odd. Let \(P_x=x\).

Proof of the validness

First, the above algorithm assigns each of \(1,2,\ldots,N\) to \(P\) exactly once, so \(P\) is indeed a permutation.

Next, let us prove by induction that the similarity of \(P\) is \(1\).

For \(N=1,2\), the algorithm constructs a permutation with the similarity of \(1\).

Consider the case \(N\geq 3\). Let \(a\) and \(b\) be the first two vertices removed in Step 2. From the assignment of \(a\) and \(b\) to \(P\), there is no path for which a longest common subsequence contains both \(a\) and \(b\). If a common subsequence contains \(a\), it follows from the assignment that such a subsequence has a length of \(1\). The same goes for \(b\).

From this, we get a problem whose size is reduced by \(2\). Repeat this to complete the proof.

---

[2] Sample implementation

Python: (using a stack instead of a queue)

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] Bonus

Write a code that judges solutions in \(\mathrm{O}(N^2)\). (Equivalent to ABC-E or F?)