2421. Number of Good Paths
這題我很有印象
是我參加的第二場的周賽的最後一題
也是我第一個沒寫出來的周賽題
所以已經寫過一次了
不過當初的文已經被砍了
這題是圖論的 connectivity 問題
可以用 union find 做（又是 union find！）
如果我們想要找出所有頭尾的值是 p 的 good path
對任意 u, v 且 vals[u] = vals[v] = p 而言
這兩點之間存在 good path 等價於：
在只考慮那些兩端的值都 <= p 的邊時這兩點是否連通
是否連通用 union find 就可
把有同樣 parent 的點收集起來
他們之間的配對有 C n 取 2 種
還要包含單獨一個點的 path
因為樹上任兩點恰有一條路徑
所以只要算有多少 u, v 之間存在 good path 即可