题目描述
There is a tree (i.e. a connected, undirected graph with no cycles) consisting of n
nodes numbered from 0
to n - 1
and exactly n - 1
edges.
You are given a 0-indexed integer array vals
of length n
where vals[i]
denotes the value of the ith
node. You are also given a 2D integer array edges
where edges[i] = [ai, bi]
denotes that there exists an undirected edge connecting nodes ai
and bi
.
A good path is a simple path that satisfies the following conditions:
The starting node and the ending node have the same value.
All nodes between the starting node and the ending node have values less than or equal to the starting node (i.e. the starting node’s value should be the maximum value along the path).
Return the number of distinct good paths.
Note that a path and its reverse are counted as the same path. For example, 0 -> 1
is considered to be the same as 1 -> 0
. A single node is also considered as a valid path.
样例
Input: vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
Output: 6
Explanation: There are 5 good paths consisting of a single node.
There is 1 additional good path: 1 -> 0 -> 2 -> 4.
(The reverse path 4 -> 2 -> 0 -> 1 is treated as the same as 1 -> 0 -> 2 -> 4.)
Note that 0 -> 2 -> 3 is not a good path because vals[2] > vals[0].
Input: vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
Output: 7
Explanation: There are 5 good paths consisting of a single node.
There are 2 additional good paths: 0 -> 1 and 2 -> 3.
Input: vals = [1], edges = []
Output: 1
Explanation: The tree consists of only one node, so there is one good path.
算法
(并查集) $O(n + m)$
类似克鲁斯卡尔算法的思想.
首先将节点按权值大小排序,这样权值相等的节点都是相邻的。我们枚举每段权值相等的节点,统计以当前节点作为起点和终点的“好路径”条数,最后把所有的条数相加即为答案。
按照上述过程,我们枚举的路径必然满足条件一,为了使路径满足条件二,我们将包含枚举这一段的左侧节点,即权值小于等于当前枚举点的点放入树中,这样,只要我们找到了联通的、起点终点权值等于当前枚举的权值的路径,这条路径上经过的点必然不超过路径两端点。
可以用并查集维护当前点的连通性,参考连通块中点的个数
C++ 代码
class Solution {
public:
vector<int> p; //p[i]表示i的父节点,路径压缩之后成为i所在集合的根节点
int find(int x) //路径压缩 + 返回根节点
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
int n = vals.size();//点的数量
vector<vector<int>> g(n);//邻接表存图
vector<int> q(n);//q[i]表示排序后排名第i的节点的下标
p.resize(n);
for(int i = 0; i < n; i ++) p[i] = q[i] = i; //初始化并查集并准备排序
sort(q.begin(), q.end(), [&](int a, int b) {
return vals[a] < vals[b];
});//按照权值大小排序
for(auto& e : edges)//建图
{
g[e[0]].push_back(e[1]);
g[e[1]].push_back(e[0]);
}
int res = 0;
for(int i = 0; i < n; i ++)
{
//[i, j - 1]这一段就是权值相同的节点
int j = i + 1;
while(j < n && vals[q[i]] == vals[q[j]]) j ++;
for(int k = i; k < j; k ++)
{
int x = q[k];
for(int y : g[x])//遍历节点x的所有边
{
if(vals[x] >= vals[y])//只有当邻点权值较小时才更新联通关系
p[find(x)] = find(y);
}
}
//将当前所有等权点按照所在连通块的父节点分类
unordered_map<int, int> hash;
for(int k = i; k < j; k ++)
hash[find(q[k])] ++;
//每一类的贡献是C(v,2) + v = C(v + 1, 2)
for(auto& [k, v] : hash)
res += (v + 1) * v / 2;
i = j - 1;
}
return res;
}
};
921/5000
有一种树(即无循环的连通无向图),它由编号从0到n - 1的n个节点和恰好n - 1条边组成。
给定一个长度为n的0索引整数数组vals,其中vals[i]表示第i个节点的值。给定一个二维整数数组边,其中边[i] = [ai, bi]表示存在一条无向边连接节点ai和bi。
好的路径是满足以下条件的简单路径:
起始节点和结束节点的值相同。
在起始节点和结束节点之间的所有节点的值都小于或等于起始节点(即起始节点的值应该是路径上的最大值)。
返回不同的良好路径的数量。
注意,路径及其反向被视为同一路径。例如,0 -> 1等同于1 -> 0。单个节点也被视为有效路径。