Count Equal-Endpoint Tree Paths Whose Interior Never Exceeds Them
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
A good simple path in the tree `edges` has equal endpoint values in `vals`, and every value along it is at most that endpoint value. Count distinct good paths, treating a path and its reverse as the same and counting every singleton node.
```cpp
class Solution {
public:
int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges);
};
```
### Examples
**Example 1:**
```text
Input: vals = [2,1,2], edges = [[0,1],[1,2]]
Output: 4
Explanation: Three singletons and the path 0-1-2 qualify.
```
**Example 2:**
```text
Input: vals = [1,2,1], edges = [[0,1],[1,2]]
Output: 3
Explanation: The two value 1 endpoints cannot connect through the larger value 2, leaving only singletons.
```
### Constraints
- `1 <= vals.length <= 30000`; `0 <= vals[i] <= 100000`.
- edges contains exactly n-1 pairs of distinct valid labels 0..n-1.
- The undirected edges form a connected acyclic tree.
### Clarifying Questions
- Do singleton nodes count? Yes, each is one good path.
- Are a path and its reverse counted separately? No.
- Can interior values equal the endpoint value? Yes; they must not exceed it.
- Can endpoints have different values? No.
```hint Check the boundary
Compare two equal-valued endpoints connected through a smaller value with the same endpoints connected through a larger value.
```
Overview: Count tree paths with equal endpoint values and no larger interior value, including singletons and counting each reverse pair once.