Count Good Paths in a Valued Tree
Each node of a tree carries a numeric label. A 'good path' connects two nodes with the same label such that no node along the way exceeds that label. Count all good paths, including single nodes.
Problem
Given a tree of n nodes (0-indexed) with an array vals of node values and a list edges, count the good paths. A good path starts and ends at nodes with equal value, and every node on the path has a value <= that endpoint value. A single node is a good path. Paths are undirected (count each unordered pair once).
Input
An array vals and a list edges of n-1 undirected [u, v] pairs forming a tree.
Output
An integer: the number of good paths.
Constraints
- 1 <= n <= 30000
- 0 <= vals[i] <= 10^5; edges forms a tree.
Examples
Example 1
Input
vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
Output
6
5 single-node paths plus the path between the two 3-valued nodes.
Example 2
Input
vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
Output
7
5 singletons plus the 1-1 path and the 2-2 path.