好路径的数
给你一棵 n 个节点的树(连通无向无环的图),节点编号从 0 到 n - 1 且恰好有 n - 1 条边。
给你一个长度为 n 下标从 0 开始的整数数组 vals ,分别表示每个节点的值。同时给你一个二维整数数组 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] 。
const int N = 30010, M = 2 * N;
class Solution {
public:
int e[M], ne[M], h[N], idx;
int p[N], sz[N];
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
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<int> id(n);// 按照vals从小到大的顺序,目的是为了让枚举的数是连通块中路径最大的点!!
for(int i = 0; i < n; i ++){
id[i] = i;
p[i] = i;
sz[i] = 1;
}
sort(id.begin(), id.end(), [&](const auto &a, const auto &b){
return vals[a] < vals[b];
});
memset(h, -1, sizeof h);
for(auto &x : edges){
add(x[0], x[1]), add(x[1], x[0]);
}
int ans = n; // 单独是一个合法点
for(int i = 0; i < n; i ++)
{
int a = id[i];
int pa = find(a); // a的祖宗节点
for(int k = h[a]; k != -1; k = ne[k]){
int b = e[k]; // a的所有邻居
int pb = find(b); //b的祖宗节点最大的点!!
if(pa == pb || vals[a] < vals[b]) continue;
//在同一个连通块表明已经计算过了可以跳过,或者邻居的值大于当前的值,可以不用考虑
//因为处在以当前节点分割的不同连通块一定构不成合法方案
if(vals[a] == vals[pb])// 如果b的祖宗节点==vals[a]意味着可以满足题意
{
ans += sz[pa] * sz[pb];// 乘法原理
sz[pa] += sz[pb];
// 此处的联通块的大小并不是真正意义的联通块大小 而是统计连通块内节点值等于 vals[a] 的节点个数
}
p[pb] = pa; // 把小的节点值合并到大的节点值上
}
}
return ans;
}
};