題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 ABC437E Sort Arrays

rating: 1245

Problem Statement

題意簡述

有 $N+1$ 個序列 $A_0, A_1, \ldots, A_N$ ，定義如下：

$A_0$ 是一個空序列 ()。
對於 $i = 1, \ldots, N$ $i = 1, \dots, N$ ，序列 $A_i$ $A_{i}$ 是將整數 $y_i$ $y_{i}$ 追加到序列 $A_{x_i}$ $A_{x_{i}}$ 的末尾 ( $0 \le x_i < i$ $0 \leq x_{i} < i$ )。
- 例如：若 $A_{x_i} = (2, 3)$ 且 $y_i = 5$ ，則 $A_i = (2, 3, 5)$ 。

請將這 $N$ 個序列 ( $A_1, \ldots, A_N$ ) 依照字典序由小到大排序後，給出由 $A_i$ 的下標 $i$ 構成的一個排列 $P = (P_1, \ldots, P_N)$ 。

如果兩個序列內容完全相同 ( $A_i = A_j$ )，則索引較小的排在前面（即若 $i < j$ ，則 $i$ 排在 $j$ 之前）。

字典序 (Lexicographical Order) 定義

序列 $S$ 字典序小於 $T$ ( $S < T$ )，若滿足以下任一條件：

$S$ 是 $T$ 的前綴，且 $S$ 的長度小於 $T$ （例如 (1, 2) < (1, 2, 3)）。
在兩者第一個數值不同的位置 $k$ ， $S_k < T_k$ （例如 (1, 2, 5) < (1, 4, 1)，因為在第 2 位 $2 < 4$ ）。

Constraints

約束條件

$1 \le N \le 3 \times 10^5$
$0 \le x_i < i$
$1 \le y_i \le 10^9$

Example

Input 1

Output 1

2 4 3 1

解釋

$A_1 = (2)$ (接在 $A_0$ 後)
$A_2 = (1)$ (接在 $A_0$ 後)
$A_3 = (1, 2)$ (接在 $A_2$ 後)
$A_4 = (1)$ (接在 $A_0$ 後)

排序後：

$A_2 = (1)$
$A_4 = (1)$ （與 $A_2$ 相等，索引較大排後）
$A_3 = (1, 2)$ （ $1$ 開頭，長度較長）
$A_1 = (2)$

故順序為 $2, 4, 3, 1$ 。

思路：在 Trie 上進行 DFS 遍歷

Trie 結構模擬

這道題目的序列生成過程本質上就是在構建一棵 Trie (字典樹)。

$A_0$ 是 Trie 的根節點。
每個操作 $(x_i, y_i)$ 代表從 Trie 節點 $x_i$ 延伸出一條邊，邊權為 $y_i$ ，到達一個新的狀態（節點）。
由於題目保證 $x_i < i$ ，這棵樹是隨著輸入依序建立的，不會有環。

直觀理解：樹結構

這個生成過程實際上構成了一棵以 $0$ 為根的樹（Trie）：

每個索引 $i$ 代表樹上的一個節點。
$A_i$ 是由 $A_{x_i}$ 延伸而來，這相當於樹上從父節點 $x_i$ 到子節點 $i$ 有一條權重為 $y_i$ 的邊。
序列 $A_i$ 的內容，就是從根節點 $0$ 走到節點 $i$ 的路徑上所有邊權組成的序列。

比較兩個序列 $A_u, A_v$ 的字典序：

前綴關係：若節點 $u$ 是節點 $v$ 的祖先，則 $A_u$ 是 $A_v$ 的前綴，故 $A_u < A_v$ 。
分歧點：若兩者在某個節點分岔，則比較分岔邊的權重 $y$ 大小。

處理相同序列

題目要求當序列相同時，索引小的排在前面。
在我們的 Trie 結構中，每個節點代表一個獨一無二的序列內容。
我們可以讓每個 Trie 節點維護一個列表 nodes，儲存所有「終止於此」的序列編號 $i$ 。
由於我們是按照 $i = 1 \sim N$ 的順序讀入並建立 Trie，對於同一個節點，其 nodes 列表中的編號自然是遞增的。

DFS 遍歷求字典序

字典序的排序對應到 Trie 上，就是 前序遍歷 (Pre-order Traversal) 的過程，但在訪問子節點時，必須按照邊權 ( $y$ ) 由小到大的順序進行。

具體流程如下：

建樹：讀取輸入，利用 mp 陣列紀錄每個編號 $i$ 對應到的 Trie 節點。若該節點不存在則建立。將 $i$ 加入該節點的 nodes 列表。
DFS：從根節點開始遍歷。
- 當到達節點 $u$ 時，首先輸出 u.nodes 中的所有編號。這是因為 $A_u$ 是其所有子樹中序列的前綴，根據字典序定義，前綴必定排在前面。
- 將 $u$ 的所有子邊按照權重 $y$ 排序。
- 依序遞迴訪問子節點。

實作細節

由於 $N$ 高達 $3 \times 10^5$ ，Python 的預設遞迴深度可能不足，需使用 sys.setrecursionlimit 或改寫為迭代形式 (Iterative DFS)。
參考程式碼中使用了迭代方式（Stack）來模擬 DFS，避免遞迴過深的問題。
使用 defaultdict 來動態建立 Trie 的邊，節省空間。

複雜度分析

時間複雜度： $\mathcal{O}(N \log N)$ $O (N lo g N)$
- 建立鄰接表（樹結構）需要 $O(N)$ 。
- 對於每個節點 $u$ ，若其有 $d_u$ 個子節點，我們需要對這些子節點進行排序，耗時 $O(d_u \log d_u)$ 。
- 總排序時間為 $\sum d_u \log d_u$ 。由於 $\sum d_u = N$ ，在最壞情況下（星狀圖），這會達到 $O(N \log N)$ 。
- DFS 遍歷每個節點一次，耗時 $O(N)$ 。
空間複雜度： $\mathcal{O}(N)$ $O (N)$
- 需要儲存鄰接表（ $N$ 個節點， $N$ 條邊），空間為 $O(N)$ 。
- DFS 的遞迴深度或迭代堆疊在最壞情況下（鏈狀圖）為 $O(N)$ 。

Code

from collections import defaultdict
import sys
sys.setrecursionlimit(int(3e5 + 5))

class TrieNode:
    __slots__ = ['child', 'nodes']
    def __init__(self):
        self.child = defaultdict(TrieNode)
        self.nodes = []

def solve():
    n = int(input())

    root = TrieNode()

    mp = [None] * (n + 1)
    mp[0] = root
    for u in range(1, n + 1):
        fa, y = map(int, input().split())
        mp[u] = mp[fa].child[y]
        mp[u].nodes.append(u)

    ans = []

    # def dfs(u: TrieNode):
    #     ans.extend(u.nodes)  # u.nodes 必定有序
    #     for _, v in sorted(u.child.items(), key=lambda x: x[0]):
    #         dfs(v)
    # dfs(root)

    st = [(root, 0)]
    while st:
        u, i = st.pop()
        if i == 0:
            ans.extend(u.nodes)
            u.child = sorted(u.child.items(), key=lambda x: x[0])
        for j in range(i, len(u.child)):
            v = u.child[j][1]
            st.append((u, i + 1))
            st.append((v, 0))
            break

    print(*ans)

if __name__ == "__main__":
    solve()

寫在最後

PROMPT

這裡什麼都沒有。