解題說明
Number of Good Paths
題目描述：
給定一棵 n 個節點的樹，每個節點有一個值 vals[i]。一條「好路徑」定義為：起點和終點的值相同，且路徑上所有節點的值都不超過起點/終點的值。求所有好路徑的數量（單一節點也算一條好路徑）。
解題思路： 使用 Union-Find + 排序 的方法：
- 將所有節點按值從小到大排序。
- 按節點值從小到大依次「加入」節點和相關的邊：只有當邊的兩個端點值都 <= 當前值時，才加入該邊（合併兩個集合）。
- 對於每個值
v，在加入所有值為v的節點和相關邊後，統計每個連通分量中有多少個值為v的節點。若某分量有c個值為v的節點，則這些節點間可形成c * (c - 1) / 2條好路徑。 - 加上每個節點自身的
n條好路徑（長度為 0）。
C++ 解法
複雜度分析
時間複雜度：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)：將邊按兩端點的最大值排序，依序加入邊並合併集合。本質與上述方法相同，但以邊為中心而非以節點為中心。
延伸思考
- 如果好路徑的條件改為「路徑上所有節點值都不小於端點值」，做法如何調整？
- 如何在一般圖（非樹）上計算好路徑數量？
- 為什麼按值從小到大處理是正確的？如果從大到小會怎樣？