ヒント：https://atcoder.jp/contests/arc211/editorial/14503

まず、\(P_1=N\) である必要があります。\(P_1\) は無視することにし、高橋くんは \(R\) を \((Q_1)\) でなく空の数列に初期化するようにし、\(Q_1\) も無視することにします。

さらに、今後の解説のため、\((Q_2,Q_3,\dots,Q_N)\) を \((-1,-2,\dots,-N+1)\) の並び替えとし、\(P\) の要素すべてに、これに応じて一様な値を加算します。以降、この設定においてある木から生成されうる数列を有効な数列と呼ぶことにします。空の数列は有効な数列であることに注意します。

木を頂点 \(1\) が根の根つき木とみなします。さて、頂点 \(1\) にいるとき、頂点 \(1\) の直接の子に割り当てる値は \((-1,-2,\dots)\) の並び替えとするのが最適です。高橋くんは割り当てられた値が最小な場所に移動するので、最小値を最大にするにはこうするほかありません。

これによって頂点 \(v\) に移動するとしましょう。すると、次に移動するのは（あれば）頂点 \(v\) の子であることがわかります（頂点 \(1\) の子でなく）。同様に割り当てて頂点 \(w\) に移動したとすると、

• 頂点 \(w\) に子があれば頂点 \(w\) の子に、
• そうでなく、頂点 \(v\) に子があれば頂点 \(v\) の子に、
• そうでなく、頂点 \(1\) に子があれば頂点 \(1\) の子に

移動することがわかります。以降繰り返すので、結局高橋くんはDFSを行うように移動します。

頂点 \(1\) の子の数を \(c\) とします。結局、有効な数列は \((-1,s_1,-2,s_2,\dots,s_{c-1},-c,s_c)\) の形（\(s_i\) は有効な数列のすべての項に \(-c+\sum_{j=1}^{i-1}|s_j|\) を足したもの）で表される数列であることがわかります。ただし、これは十分条件ではありません。

すぬけくんは子の順番を自由に決めれますから、辞書順が最大になるように決めます。これは、子から生成される有効な数列の末尾に \(0\) を追加したものを辞書順の降順に並び替えた順番、が最適であることが比較的素直な考察でわかります。これが必要十分条件になりますから、あとは判定すればよいです。

区間の最大値、最小値を得ることのできるデータ構造と、ある値の位置をすぐに得ることのできる配列を用意しておくとよいでしょう。もっとも難しいのは正しく辞書順に並んでいるか判定するところだと思います。ここは、余計なところを調べずに素直に調べればよく、これだけでマージテクの要領で計算量を落とせます（マージテクについては ABC329-Fの解説を参照）。

時間計算量は \(O(N\log N)\) で、十分高速です。

実装例 (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!: 入力を作ってください。すなわち、\(N\) 頂点の木があるとき、高橋君が出力する数列をまともな速度で作るアルゴリズムを作ってください。