Overview of the solution

Since the goal is to find the lexicographically smallest, we solve this problem using a greedy method that tries to minimize the value of each term from the beginning of the sequence.

When minimizing the \(i\)-th term of \(A(P)\), we are basically constrained by this requirement: “\(x\) must be written on some vertex adjacent to vertex \(i\).”

We can ultimately obtain the lexicographically smallest sequence by repeatedly minimizing the \((i+1)\)-th term while adhering to the constraints for minimizing the \(1\)-st to \(i\)-th terms. Handling isolated vertices and minimizing the \((i+1)\)-th term while adhering to the constraints are somewhat complex, so details are provided below.

Details of the solution

First, let’s clarify the terms used in the following explanation.

Terms used below

• Assume that the edge connecting vertex \(i\) and vertex \(j\) is removed during the \(i\)-th operation. If such a vertex \(j\) has already been determined, we call vertex \(i\) a confirmed vertex; otherwise, we call vertex \(i\) an unconfirmed vertex. Furthermore, for a confirmed vertex \(i\), we call vertex \(j\) the target of vertex \(i\).

• When there is a constraint that requires writing \(x\) on some vertex \(v\) adjacent to vertex \(i\), and there are two or more adjacent vertices, we say that \(x\) is provisionally placed on vertex \(v\). We also call vertex \(i\) the source of the provisional placement for vertex \(v\).

The solution

Each time vertex \(i\) becomes a confirmed vertex, we actually cut the edge and write the value on its target vertex \(j\). We also note that the provisional placement may be removed due to vertex \(i\) becoming confirmed.

Let’s consider how to minimize the \(i\)-th term while satisfying the provisional placement constraints.

Determining if \(A_i = 0\) is possible

If vertex \(i\) is already isolated, we can set \(A_i = 0\). Otherwise, if the degree of vertex \(i\) is two or more, it can be shown that \(A_i = 0\) is impossible. (Proof is described later.)

Let’s consider the case where the degree of vertex \(i\) is one. Let \(j\) be the vertex connected to vertex \(i\). Then, to set \(A_i = 0\), it is necessary that \(i > j\).

This is because if \(i < j\), the edge between \(i\) and \(j\) will always remain until the operation for vertex \(i\) is performed. Similarly, vertex \(j\) must be an unconfirmed vertex.

Conversely, if \(j < i\) and vertex \(j\) is unconfirmed, we can set \(A_i = 0\) by making vertex \(j\) the target of vertex \(i\).

If \(A_i = 0\) is impossible

For each vertex \(j\) adjacent to vertex \(i\), check whether \(j\) has a provisional placement or a value written on it.

1. If no adjacent vertex has a provisional placement or a written value

In this case, \(A_i\) cannot be an integer contained in the first \(i-1\) terms because those integers are provisionally placed on or written on vertices not adjacent to vertex \(i\).

Thus, it is optimal to set \(A_i\) to the smallest positive integer not contained in the first \(i-1\) terms (let’s call this \(x\)).

If the degree of vertex \(i\) is one, the target of vertex \(i\) is confirmed to be the adjacent vertex \(t\), and \(x\) is written on vertex \(t\).

If the degree is two or more, \(x\) should be provisionally placed on each vertex adjacent to vertex \(i\).

2. If there is an adjacent vertex with a provisional placement or a written value

Among such vertices, select the one with the smallest value (either provisionally placed or written), call this vertex \(t\), and the value on \(t\) (either provisionally placed or written) \(x\).

Such a vertex \(t\) is uniquely determined (if it exists) since the input graph is a tree.

The same discussion as in 1. shows that the minimum value for \(A_i\) is \(x\). The target of vertex \(i\) should be \(t\).

Here, if vertex \(t\) is under provisional placement, let \(s\) be the source of the provisional placement for vertex \(t\), and the target of vertex \(s\) must be \(t\), so vertex \(s\) is also confirmed.

Corner case 1: Chain of confirmations

If minimizing the \(i\)-th term makes vertex \(i\) confirmed, the degree of its target vertex \(j\) decreases. Here, care must be taken if vertex \(j\) is an unconfirmed vertex satisfying \(j < i\) and its degree becomes one.

Provisional placement is only allowed when the degree is two or more. Since an edge must be cut unless the vertex is isolated, if the degree becomes one, vertex \(j\) must be confirmed. Be aware of such chains of confirmations.

Corner case 2: Special case with degree two

In 2. of the cases where \(A_i = 0\) is not possible, we said we would select the vertex with the smallest value (either provisionally placed or written). However, in reality, an undetermined vertex \(j\) with a degree of two that is adjacent to vertex \(i\) and satisfies \(j < i\) should not be included as a candidate in 2.

The reason is as follows. If the source of the provisional placement for vertex \(j\) is \(k\) and the provisionally placed value is \(x\), it seems possible to achieve \(A_k = A_i = x\) by writing \(x\) on \(j\). However, in reality, cutting the edge \(k-j\) reduces the degree of \(j\) to one, and the target of vertex \(j\) is confirmed to be \(i\), making it impossible to achieve \(A_i = x\) because the edge \(j-i\) ends up being cut before the operation for vertex \(i\).

Summary

By minimizing \(A_i\) in the order \(i=1,2,\ldots,N\) while paying attention to these corner cases, we can obtain the lexicographically smallest sequence \(A\).

All of the above processes can be implemented in \(\mathrm{O}(N\log N)\).

---

[Proof that \(A_i = 0\) is impossible if the degree of vertex \(i\) is two or more]

Because it is not the case that two or more different values are provisionally placed on vertex \(i\) when processing it, if the degree is two or more, there is at least one confirmed vertex or a vertex with a larger vertex number than \(i\) adjacent to it. Thus, it is impossible to set \(A_i = 0\) if the degree of vertex \(i\) is two or more.