Hints: https://atcoder.jp/contests/arc211/editorial/14696

First, \(P_1=N\) is necessary. We will ignore \(P_1\), have Takahashi initialize \(R\) with an empty sequence instead of \((Q_1)\), and ignore \(Q_1\) as well.

Furthermore, for the following explanation, we treat \((Q_2,Q_3,\dots,Q_N)\) as a rearrangement of \((-1,-2,\dots,-N+1)\), and add a uniform value to all elements of \(P\) accordingly. Hereafter, we will call a sequence that can be generated from some tree under this setting a valid sequence. Note that the empty sequence is a valid sequence.

Consider the tree as a rooted tree with vertex \(1\) as the root. Now, when at vertex \(1\), it is optimal to assign values to the immediate children of vertex \(1\) as a rearrangement of \((-1,-2,\dots)\). Since Takahashi moves to the location with the minimum assigned value, to maximize the minimum value, there is no choice but to do this.

Suppose we move to vertex \(v\) by this. Then, it can be seen that the next move is to a child of vertex \(v\) (if it exists) (not a child of vertex \(1\)). If we similarly assign and move to vertex \(w\), then it can be seen that we move as follows:

• if vertex \(w\) has children, move to a child of vertex \(w\);
• otherwise, if vertex \(v\) has children, move to a child of vertex \(v\);
• otherwise, if vertex \(1\) has children, move to a child of vertex \(1\).

It repeats thereafter, so Takahashi eventually moves as if performing DFS.

Let \(c\) be the number of children of vertex \(1\). Eventually, it can be seen that a valid sequence is a sequence of the form \((-1,s_1,-2,s_2,\dots,s_{c-1},-c,s_c)\) (where \(s_i\) is a valid sequence with \(-c+\sum_{j=1}^{i-1}|s_j|\) added to all terms). However, this is not a sufficient condition.

Since Snuke can freely decide the order of children, he decides so that the lexicographic order is maximum. It can be seen through relatively straightforward consideration that the order obtained by sorting in descending lexicographic order the valid sequences generated from children with \(0\) added to the end is optimal. This becomes a necessary and sufficient condition, so we just need to judge this.

It will be useful to prepare a data structure that can obtain the maximum and minimum values of an interval, and an array that can immediately obtain the position of a certain value. The most difficult part is probably judging whether they are correctly arranged in lexicographic order. Here, we should examine straightforwardly without examining unnecessary parts, and with this alone we can reduce the computational complexity in the manner of “merge technique” (for merge technique, see the editorial of ABC329-F).

The time complexity is \(O(N\log N)\), which is sufficiently fast.

Implementation Example (Python (Codon 0.19.3), 56ms)

def check(lf, ri, mx):
    if lf == ri:
        return "Yes"
    
    sep = [lf]
    now = P[lf] + 1

    while now <= mx:
        if sep[-1] > pos[now]:
            return "No"
        if lf <= pos[now] < ri:
            sep.append(pos[now])
        else:
            return "No"
        now += 1

    n = len(sep)
    sep.append(ri)
    lgt = [(sep[i + 1] - sep[i] - 1) for i in range(n)]

    mxl = (-1, -1)
    for i in range(n):
        mxl = max(mxl, (lgt[i], i))

    nmx = P[lf] - 1

    for i in range(n):
        if i < n - 1:
            flg = False
            for j in range(min(lgt[i], lgt[i + 1])):
                if P[sep[i] + j + 1] - lgt[i] < P[sep[i + 1] + j + 1]:
                    return "No"
                elif P[sep[i] + j + 1] - lgt[i] > P[sep[i + 1] + j + 1]:
                    flg = True
                    break

            if not flg:
                if lgt[i] > lgt[i + 1]:
                    return "No"

        if mxl[1] != i:
            for j in range(sep[i] + 1, sep[i + 1]):
                if not nmx - lgt[i] < P[j] <= nmx:
                    return "No"

        if check(sep[i] + 1, sep[i + 1], nmx) == "No":
            return "No"
        nmx -= lgt[i]

    return "Yes"

T = int(input())
for _ in range(T):
    N = int(input())
    P = list(map(int, input().split()))
    pos = [0] * N

    for i in range(N):
        P[i] -= 1
        pos[P[i]] = i

    if P[0] == N - 1:
        print(check(1, N, N - 2))
    else:
        print("No")

Bonus!: Create the input. That is, when there is a tree with \(N\) vertices, create an algorithm that produces the sequence output by Takahashi at a reasonable speed.