題目描述:
給定一棵 n 個節點的樹,每個節點有一個值 vals[i]。一條「好路徑」定義為:起點和終點的值相同,且路徑上所有節點的值都不超過起點/終點的值。求所有好路徑的數量(單一節點也算一條好路徑)。
解題思路: 使用 Union-Find + 排序 的方法:
v,在加入所有值為 v 的節點和相關邊後,統計每個連通分量中有多少個值為 v 的節點。若某分量有 c 個值為 v 的節點,則這些節點間可形成 c * (c - 1) / 2 條好路徑。n 條好路徑(長度為 0)。時間複雜度:O(n * alpha(n)) 近似 O(n) — 排序 O(n log n),Union-Find 操作幾乎為常數時間。
空間複雜度:O(n) — Union-Find 陣列和鄰接表。
1. Initialize Union-Find with n singleton sets
2. Build adjacency list
3. Group nodes by value, process in ascending order
4. For each value v and its nodes:
a. For each node u with value v:
- For each neighbor w of u:
- If vals[w] <= v: union(u, w)
b. Count how many value-v nodes share each component root
c. For each component with c value-v nodes: ans += c*(c-1)/2
5. Return ans + n (including single-node paths)DFS/BFS 暴力法 O(n^2):對每對相同值的節點檢查路徑上所有節點值是否合法。時間複雜度過高。
Kruskal 風格 + 排序 O(n log n):將邊按兩端點的最大值排序,依序加入邊並合併集合。本質與上述方法相同,但以邊為中心而非以節點為中心。