2023-08-08：给你一棵 n 个节点的树（连通无向无环的图） 节点编号从 0 到 n - 1 且恰好有 n - 1 条边

2023-08-08：给你一棵 n 个节点的树（连通无向无环的图）

节点编号从 0 到 n - 1 且恰好有 n - 1 条边

给你一个长度为 n 下标从 0 开始的整数数组 vals

分别表示每个节点的值

同时给你一个二维整数数组 edges

其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边

一条 好路径 需要满足以下条件：

开始节点和结束节点的值 相同 。

开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值。

（也就是说开始节点的值应该是路径上所有节点的最大值）。

请你返回不同好路径的数目。

注意，一条路径和它反向的路径算作 同一 路径。

比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。

输入：vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]。

输出：7。

来自谷歌。

来自左神

答案2023-08-08：

大致的步骤如下：

1.创建一个图（树）数据结构，并初始化节点的值和连接关系。

2.对节点的值进行排序，按照值的大小顺序处理节点。

3.初始化并查集，用于管理节点的连通性。

4.创建一个数组记录每个连通分量中值最大的节点的索引。

5.创建一个数组记录每个连通分量中值最大的节点所在连通分量的节点数。

6.初始化答案为节点的总数。

7.遍历排序后的节点列表，依次处理每个节点：

7.1.获取当前节点的索引和值。

7.2.查找当前节点的连通分量代表节点。

7.3.查找当前连通分量代表节点的最大值节点的索引。

7.4.遍历当前节点的邻居节点，将邻居节点的值与当前节点值进行比较。

7.5.若邻居节点的值小于等于当前节点值，并且邻居节点所在的连通分量与当前连通分量不同，则进行以下操作：

7.5.1.查找邻居节点连通分量的代表节点的最大值节点的索引。 7.5.2.若邻居节点的值等于该最大值节点的值，则更新答案并累加该最大值节点所在连通分量的节点数。 7.5.3.合并当前节点和邻居节点所在的连通分量。 7.5.4.更新当前连通分量代表节点的索引。

8.返回答案。

时间复杂度为O(nlogn)。 空间复杂度为O(n)。

go完整代码如下：

在这里插入图片描述rust完整代码如下：

在这里插入图片描述c++完整代码如下：

在这里插入图片描述c完整代码如下：

在这里插入图片描述