2867. Count Valid Paths in a Tree Hard

1/**
2 * [2867] Count Valid Paths in a Tree
3 *
4 * 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.
5 * Return the number of valid paths in the tree.
6 * A path (a, b) is valid if there exists exactly one prime number among the node labels in the path from a to b.
7 * Note that:
8 * 
9 * 	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.
10 * 	Path (a, b) and path (b, a) are considered the same and counted only once.
11 * 
12 *  
13 * <strong class="example">Example 1:
14 * <img alt="" src="https://assets.leetcode.com/uploads/2023/08/27/example1.png" style="width: 440px; height: 357px;" />
15 * Input: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]
16 * Output: 4
17 * Explanation: The pairs with exactly one prime number on the path between them are: 
18 * - (1, 2) since the path from 1 to 2 contains prime number 2. 
19 * - (1, 3) since the path from 1 to 3 contains prime number 3.
20 * - (1, 4) since the path from 1 to 4 contains prime number 2.
21 * - (2, 4) since the path from 2 to 4 contains prime number 2.
22 * It can be shown that there are only 4 valid paths.
23 * 
24 * <strong class="example">Example 2:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2023/08/27/example2.png" style="width: 488px; height: 384px;" />
26 * Input: n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]]
27 * Output: 6
28 * Explanation: The pairs with exactly one prime number on the path between them are: 
29 * - (1, 2) since the path from 1 to 2 contains prime number 2.
30 * - (1, 3) since the path from 1 to 3 contains prime number 3.
31 * - (1, 4) since the path from 1 to 4 contains prime number 2.
32 * - (1, 6) since the path from 1 to 6 contains prime number 3.
33 * - (2, 4) since the path from 2 to 4 contains prime number 2.
34 * - (3, 6) since the path from 3 to 6 contains prime number 3.
35 * It can be shown that there are only 6 valid paths.
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	1 <= n <= 10^5
41 * 	edges.length == n - 1
42 * 	edges[i].length == 2
43 * 	1 <= ui, vi <= n
44 * 	The input is generated such that edges represent a valid tree.
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/count-valid-paths-in-a-tree/
50// discuss: https://leetcode.com/problems/count-valid-paths-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn count_paths(n: i32, edges: Vec<Vec<i32>>) -> i64 {
56        
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_2867() {
68    }
69}
70