{"id":355712,"date":"2024-05-20T23:14:31","date_gmt":"2024-05-20T23:14:31","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=355712"},"modified":"-0001-11-30T00:00:00","modified_gmt":"2024-05-20T23:14:31","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=355712","title":{"rendered":"LeetCode, Hard++ (Acceptance 24%, Latest): 2867. Count Valid Paths in a Tree. DFS. O(n). Swift<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

Description<\/h3>\n

There is an undirected tree with n nodes labeled from 1 to n. You are given the integer n and a 2D integer array edges of length n — 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree.<\/p>\n

Return the number of valid paths in the tree.<\/p>\n

A path (a, b) is valid if there exists exactly one prime number among the node labels in the path from a to b.<\/p>\n

Note that:
The path (a, b) is a sequence of distinct nodes starting with node a and ending with node b such that every two adjacent nodes in the sequence share an edge in the tree.
Path (a, b) and path (b, a) are considered the same and counted only once.<\/p>\n

Example 1:<\/p>\n

Input: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]] Output: 4 Explanation: The pairs with exactly one prime number on the path between them are:  - (1, 2) since the path from 1 to 2 contains prime number 2.  - (1, 3) since the path from 1 to 3 contains prime number 3. - (1, 4) since the path from 1 to 4 contains prime number 2. - (2, 4) since the path from 2 to 4 contains prime number 2. It can be shown that there are only 4 valid paths.<\/code><\/pre>\n
Example 2:<\/p>\n
Input: n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]] Output: 6 Explanation: The pairs with exactly one prime number on the path between them are:  - (1, 2) since the path from 1 to 2 contains prime number 2. - (1, 3) since the path from 1 to 3 contains prime number 3. - (1, 4) since the path from 1 to 4 contains prime number 2. - (1, 6) since the path from 1 to 6 contains prime number 3. - (2, 4) since the path from 2 to 4 contains prime number 2. - (3, 6) since the path from 3 to 6 contains prime number 3. It can be shown that there are only 6 valid paths.<\/code><\/pre>\n
Constraints<\/strong>:
1 <= n <= 10^5
edges.length == n — 1
edges[i].length == 2
1 <= u(i), v(i) <= n
The input is generated such that edges represent a valid tree.<\/p>\n
Intuition<\/h3>\n
The intuition is to employ a depth-first search (DFS) approach through the tree.<\/p>\n
Approach<\/h3>\n
During each step in the traversal, we perform the following key calculations:<\/p>\n
    \n
  1. \n
    Determine the path that ends at the current node.<\/p>\n<\/li>\n
  2. \n
    Compute two different subtree paths that traverse the current node.<\/p>\n<\/li>\n
  3. \n
    Maintain an array that keeps track of the cases where paths contain either 0 or 1 prime number.<\/p>\n<\/li>\n<\/ol>\n
    This method allows us to efficiently count the valid paths in the tree while considering the presence of prime numbers.<\/p>\n
    Complexity<\/h3>\n