Hard
题目描述
有一棵树（即一个连通、无向、无环图），由 n 个编号从 0 到 n - 1 的节点组成，恰好有 n - 1 条边。
给你一个长度为 n 的整数数组 vals，其中 vals[i] 表示第 i 个节点的值。同时给你一个二维整数数组 edges，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间存在一条无向边。
一条 好路径 是满足下述条件的一条简单路径：
- 开始节点和结束节点的值相同。
- 开始节点和结束节点之间的所有节点值都 小于或等于 开始节点的值（也就是说，开始节点的值应该是路径上的最大值）。
返回不同 好路径 的数目。
注意，一条路径和它的反向路径被视为 同一 条路径。例如，0 -> 1 被认为与 1 -> 0 相同。单个节点也被认为是一条有效的路径。
示例 1：
输入：vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
输出：6
解释：有 5 条由单个节点组成的好路径。
还有 1 条额外的好路径：1 -> 0 -> 2 -> 4。
（反向路径 4 -> 2 -> 0 -> 1 被视为与 1 -> 0 -> 2 -> 4 相同。）
注意 0 -> 2 -> 3 不是一条好路径，因为 vals[2] > vals[0]。
示例 2：
输入：vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
输出：7
解释：有 5 条由单个节点组成的好路径。
还有 2 条额外的好路径：0 -> 1 和 2 -> 3。
示例 3：
输入：vals = [1], edges = []
输出：1
解释：树只有一个节点，所以有一条好路径。
提示：
n == vals.length1 <= n <= 3 * 10^40 <= vals[i] <= 10^5edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedges表示一棵有效的树。
解题思路
这是一道典型的并查集（Union-Find）与排序结合的树形问题。
核心思路：
- 从小到大处理节点：按节点值从小到大的顺序处理，确保在处理某个值的节点时，已经处理过所有更小值的节点。
- 构建连通分量：对于相同值的节点，通过并查集维护它们之间的连通性。只有当路径上所有节点值都不超过端点值时，两个相同值的节点才可能通过好路径连接。
- 计算好路径数量：对于每个连通分量中有 k 个相同值的节点，它们之间的好路径数量为
k * (k + 1) / 2（包括单节点路径）。
算法步骤：
- 将节点按值分组并排序
- 按值从小到大处理每组节点
- 对于当前值的节点，检查它们与已处理的相邻节点的连接关系
- 使用并查集合并可连通的节点
- 统计每个连通分量中相同值节点的数量，计算好路径数
时间复杂度： O(n log n)，主要是排序的复杂度 空间复杂度： O(n)，存储并查集和邻接表
代码实现
class Solution {
public:
vector<int> parent;
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
parent[y] = x;
}
}
int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
int n = vals.size();
parent.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
vector<vector<int>> graph(n);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
}
map<int, vector<int>> valueToNodes;
for (int i = 0; i < n; i++) {
valueToNodes[vals[i]].push_back(i);
}
vector<bool> active(n, false);
int result = 0;
for (auto& [val, nodes] : valueToNodes) {
for (int node : nodes) {
for (int neighbor : graph[node]) {
if (active[neighbor] && vals[neighbor] <= val) {
unite(node, neighbor);
}
}
active[node] = true;
}
unordered_map<int, int> componentCount;
for (int node : nodes) {
componentCount[find(node)]++;
}
for (auto& [root, count] : componentCount) {
result += count * (count + 1) / 2;
}
}
return result;
}
};
class Solution:
def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
n = len(vals)
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def unite(x, y):
px, py = find(x), find(y)
if px != py:
parent[py] = px
graph = [[] for _ in range(n)]
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
value_to_nodes = defaultdict(list)
for i, val in enumerate(vals):
value_to_nodes[val].append(i)
active = [False] * n
result = 0
for val in sorted(value_to_nodes.keys()):
nodes = value_to_nodes[val]
for node in nodes:
for neighbor in graph[node]:
if active[neighbor] and vals[neighbor] <= val:
unite(node, neighbor)
active[node] = True
component_count = defaultdict(int)
for node in nodes:
component_count[find(node)] += 1
for count in component_count.values():
result += count * (count + 1) // 2
return result
public class Solution {
private int[] parent;
private int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
private void Unite(int x, int y) {
int px = Find(x), py = Find(y);
if (px != py) {
parent[py] = px;
}
}
public int NumberOfGoodPaths(int[] vals, int[][] edges) {
int n = vals.Length;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var edge in edges) {
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
var valueToNodes = new SortedDictionary<int, List<int>>();
for (int i = 0; i < n; i++) {
if (!valueToNodes.ContainsKey(vals[i])) {
valueToNodes[vals[i]] = new List<int>();
}
valueToNodes[vals[i]].Add(i);
}
bool[] active = new bool[n];
int result = 0;
foreach (var kvp in valueToNodes) {
int val = kvp.Key;
var nodes = kvp.Value;
foreach (int node in nodes) {
foreach (int neighbor in graph[node]) {
if (active[neighbor] && vals[neighbor] <= val) {
Unite(node, neighbor);
}
}
active[node] = true;
}
var componentCount = new Dictionary<int, int>();
foreach (int node in nodes) {
int root = Find(node);
componentCount[root] = componentCount.GetValueOrDefault(root, 0) + 1;
}
foreach (int count in componentCount.Values) {
result += count * (count + 1) / 2;
}
}
return result;
}
}
var numberOfGoodPaths = function(vals, edges) {
const n = vals.length;
const parent = Array.from({length: n}, (_, i) => i);
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
function unite(x, y) {
const px = find(x), py = find(y);
if (px !== py) {
parent[py] = px;
}
}
const graph = Array.from({length: n}, () => []);
for (const [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
const valueToNodes = new Map();
for (let i = 0; i < n; i++) {
if (!valueToNodes.has(vals[i])) {
valueToNodes.set(vals[i], []);
}
valueToNodes.get(vals[i]).push(i);
}
const active = new Array(n).fill(false);
let result = 0;
const sortedValues = [...valueToNodes.keys()].sort((a, b) => a - b);
for (const val of sortedValues) {
const nodes = valueToNodes.get(val);
for (const node of nodes) {
for (const neighbor of graph[node]) {
if (active[neighbor] && vals[neighbor] <= val) {
unite(node, neighbor);
}
}
active[node] = true;
}
const componentCount = new Map();
for (const node of nodes) {
const root = find(node);
componentCount.set(root, (componentCount.get(root) || 0) + 1);
}
for (const count of componentCount.values()) {
result += count * (count + 1) / 2;
}
}
return result;
};
复杂度分析
| 复杂度类型 | 大小 |
|---|---|
| 时间复杂度 | O(n log n) |
| 空间复杂度 | O(n) |