TheRealSamuel/LeetCodeProblem

1{2    "id": 2505,3    "name": "number_of_good_paths",4    "difficulty": "Hard",5    "link": "https://leetcode.com/problems/number-of-good-paths/",6    "date": "1663459200000",7    "task_description": "There is a tree (i.e. a connected, undirected graph with no cycles) consisting of `n` nodes numbered from `0` to `n - 1` and exactly `n - 1` edges. You are given a **0-indexed** integer array `vals` of length `n` where `vals[i]` denotes the value of the `ith` node. You are also given a 2D integer array `edges` where `edges[i] = [ai, bi]` denotes that there exists an **undirected** edge connecting nodes `ai` and `bi`. A **good path** is a simple path that satisfies the following conditions: The starting node and the ending node have the **same** value. All nodes between the starting node and the ending node have values **less than or equal to** the starting node (i.e. the starting node's value should be the maximum value along the path). Return _the number of distinct good paths_. Note that a path and its reverse are counted as the **same** path. For example, `0 -> 1` is considered to be the same as `1 -> 0`. A single node is also considered as a valid path. **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. ``` **Constraints:** `n == vals.length` `1 <= n <= 3 * 104` `0 <= vals[i] <= 105` `edges.length == n - 1` `edges[i].length == 2` `0 <= ai, bi < n` `ai != bi` `edges` represents a valid tree.",8    "public_test_cases": [9        {10            "label": "Example 1",11            "input": "vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]",12            "output": "6 "13        },14        {15            "label": "Example 2",16            "input": "vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]",17            "output": "7 "18        },19        {20            "label": "Example 3",21            "input": "vals = [1], edges = []",22            "output": "1 "23        }24    ],25    "private_test_cases": [],26    "haskell_template": "numberOfGoodPaths :: [Int] -> [[Int]] -> Int\nnumberOfGoodPaths vals edges ",27    "ocaml_template": "let numberOfGoodPaths (vals: int list) (edges: int list list) : int =  ",28    "scala_template": "def numberOfGoodPaths(vals: List[Int],edges: List[List[Int]]): Int = { \n    \n}",29    "java_template": "public static int numberOfGoodPaths(List<Integer> vals, List<List<Integer>> edges) {\n\n}",30    "python_template": "class Solution(object):\n    def numberOfGoodPaths(self, vals, edges):\n        \"\"\"\n        :type vals: List[int]\n        :type edges: List[List[int]]\n        :rtype: int\n        \"\"\"\n        "31}