AtCoder 🟡 ABC437E Sort Arrays

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

🔗 🟡 ABC437E Sort Arrays

Problem Statement

題意簡述

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

• $A_0$ 是一個空序列 ()。
• 對於 $i = 1, \ldots, N$，序列 $A_i$ 是將整數 $y_i$ 追加到序列 $A_{x_i}$ 的末尾 ($0 \le 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$)，若滿足以下任一條件：

1. $S$ 是 $T$ 的前綴，且 $S$ 的長度小於 $T$ （例如 (1, 2) < (1, 2, 3)）。
2. 在兩者第一個數值不同的位置 $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

4
0 2
0 1
2 2
0 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$ 後)

排序後：

1. $A_2 = (1)$
2. $A_4 = (1)$ （與 $A_2$ 相等，索引較大排後）
3. $A_3 = (1, 2)$ （$1$ 開頭，長度較長）
4. $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$ 的字典序：

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

處理相同序列

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

DFS 遍歷求字典序

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

具體流程如下：

1. 建樹：讀取輸入，利用 mp 陣列紀錄每個編號 $i$ 對應到的 Trie 節點。若該節點不存在則建立。將 $i$ 加入該節點的 nodes 列表。
2. 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)$。
  • 對於每個節點 $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)$
  • 需要儲存鄰接表（$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()