An undirected tree has n nodes labeled from 0 to n - 1. The array vals gives each node's value, and each pair [u, v] in edges connects two nodes.
A path is good when its endpoints have equal values and no node along the path has a larger value than those endpoints. A path cannot visit a node more than once.
Return the number of distinct good paths. Every single node counts as a good path. Count a path and its reverse only once.
Diagram nodes show node index:value.
Example 1:
Input: vals = [2,1,2]
edges = [[0,1],[1,2]]
Output: 4Explanation: The three single-node paths are good. The path 0 → 1 → 2 is also good: its endpoints both have value 2, and the middle node has value 1. These are the 4 distinct good paths.
Example 2:
Input: vals = [1,3,1]
edges = [[0,1],[1,2]]
Output: 3Explanation: Each single node forms a good path. The path between nodes 0 and 2 is not good because its middle value, 3, exceeds their value of 1. Thus only the 3 single-node paths count.
Example 3:
Input: vals = [4,4,4]
edges = [[0,1],[0,2]]
Output: 6Explanation: All values are equal, so every path is good. There are 3 single-node paths and 3 paths connecting pairs of distinct nodes, for a total of 6.
Constraints:
n == vals.length1 <= n <= 300000 <= vals[i] <= 100000edges.length == n - 1- Each edge contains two distinct integer node labels between
0andn - 1. - The edges form a connected, undirected tree.