[1] Range of \(f(P)\)

Let’s find the range of possible values for \(f(P)\). Let \(d_i\) denote the distance from vertex \(1\) to vertex \(i\), then it can be seen that \(g_i\) takes values from \(1\) to \(d_i + 1\).

From this, it can be seen that the range of \(f(P)\) is from \(N\) to \(N+\sum_{i=1}^N d_i\). If \(K\) is outside this range, the answer is No. In fact, if \(K\) is within this range, there is always a \(P\) such that \(f(P)=K\).

[2] Reduction to a Subset Sum Problem

Regarding the length of the Longest Increasing Subsequence (LIS), the following holds:

• When an element is added to the end of the sequence, the length of the LIS either remains the same or increases by \(1\).

Let \(w_i\) be the size of the subtree rooted at vertex \(i\). If we decide on a set of vertices \(S=\lbrace s_1,\ldots,s_k\rbrace\) for which adding \(P_{s_i}\) to the end increases the length of the LIS, the value of \(f(P)\) can be calculated as

\[ f(P)=N+\sum_{i=1}^k w_{s_i}\]

Thus, the problem is reduced to whether we can select some of the \(N-1\) elements \(w_2,\ldots,w_N\) to make their sum equal to \(K-N\). (The method to construct \(P\) that achieves the decided \(S\) will be described later.)

This is exactly a subset sum problem. However, it is generally hard to solve fast.

[3] Utilizing the Properties of \(w_i\)

In this problem, \(w_i\) had the special constraint of being the size of a subtree. By using this property, we can greedily solve the subset sum problem.

Specifically, the following greedy approach is valid: sort \(w_i\) in descending order and select the current element if the sum does not exceed \(K-N\). The validity of this approach can be shown by induction on the size of the tree.

[4] How to Construct \(P\)

Having determined \(S\) in [3], we now need to find a permutation \(P\) such that the set of vertices for which adding \(P_{s_i}\) to the end increases the length of the LIS is \(S\).

There are various ways to construct this, and here we introduce the writer’s method.

For \(i=1,2,\ldots,N\), define \(x_i\) as \(x_i:=d_i\) if \(i\in S\), and \(x_i:=-d_i\) if \(i\notin S\). Assign \(1,2,\ldots,N\) to \(P_i\) in ascending order of \(x_i\), and it can be confirmed that this \(P\) indeed satisfies the condition.

The computational complexity is dominated by sorting and is \(\mathrm{O}(N\log N)\).