#2421
Number of Good Paths
expert · 1265 · lc hard +32 · verified · 56.3% accepted · 2,445 likes · top 50%
Description
An undirected tree of n nodes (labeled 0 to n - 1) has node values given by vals and edges given by edges. A path between two nodes is good if:
- Every node on the path has the same value, and
- The two endpoints have the same value.
Return the number of distinct good paths.
Example 1:
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].
Example 2:
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.
Example 3:
Input: vals = [1], edges = []
Output: 1
Explanation: The tree consists of only one node, so there is one good path.
Code
1
2
3