3820. Pythagorean Distance Nodes in a Tree Medium

1/**
2 * [3820] Pythagorean Distance Nodes in a Tree
3 *
4 * You are given an integer n and an undirected tree with n nodes numbered from 0 to n - 1. The tree is represented by a 2D array edges of length n - 1, where edges[i] = [ui, vi] indicates an undirected edge between ui and vi.
5 * You are also given three distinct target nodes x, y, and z.
6 * For any node u in the tree:
7 * 
8 * 	Let dx be the distance from u to node x
9 * 	Let dy be the distance from u to node y
10 * 	Let dz be the distance from u to node z
11 * 
12 * The node u is called special if the three distances form a Pythagorean Triplet.
13 * Return an integer denoting the number of special nodes in the tree.
14 * A Pythagorean triplet consists of three integers a, b, and c which, when sorted in ascending order, satisfy a^2 + b^2 = c^2.
15 * The distance between two nodes in a tree is the number of edges on the unique path between them.
16 *  
17 * <strong class="example">Example 1:
18 * <div class="example-block">
19 * Input: <span class="example-io">n = 4, edges = [[0,1],[0,2],[0,3]], x = 1, y = 2, z = 3</span>
20 * Output: <span class="example-io">3</span>
21 * Explanation:
22 * For each node, we compute its distances to nodes x = 1, y = 2, and z = 3.
23 * 
24 * 	Node 0 has distances 1, 1, and 1. After sorting, the distances are 1, 1, and 1, which do not satisfy the Pythagorean condition.
25 * 	Node 1 has distances 0, 2, and 2. After sorting, the distances are 0, 2, and 2. Since 0^2 + 2^2 = 2^2, node 1 is special.
26 * 	Node 2 has distances 2, 0, and 2. After sorting, the distances are 0, 2, and 2. Since 0^2 + 2^2 = 2^2, node 2 is special.
27 * 	Node 3 has distances 2, 2, and 0. After sorting, the distances are 0, 2, and 2. This also satisfies the Pythagorean condition.
28 * 
29 * Therefore, nodes 1, 2, and 3 are special, and the answer is 3.
30 * </div>
31 * <strong class="example">Example 2:
32 * <div class="example-block">
33 * Input: <span class="example-io">n = 4, edges = [[0,1],[1,2],[2,3]], x = 0, y = 3, z = 2</span>
34 * Output: <span class="example-io">0</span>
35 * Explanation:
36 * For each node, we compute its distances to nodes x = 0, y = 3, and z = 2.
37 * 
38 * 	Node 0 has distances 0, 3, and 2. After sorting, the distances are 0, 2, and 3, which do not satisfy the Pythagorean condition.
39 * 	Node 1 has distances 1, 2, and 1. After sorting, the distances are 1, 1, and 2, which do not satisfy the Pythagorean condition.
40 * 	Node 2 has distances 2, 1, and 0. After sorting, the distances are 0, 1, and 2, which do not satisfy the Pythagorean condition.
41 * 	Node 3 has distances 3, 0, and 1. After sorting, the distances are 0, 1, and 3, which do not satisfy the Pythagorean condition.
42 * 
43 * No node satisfies the Pythagorean condition. Therefore, the answer is 0.
44 * </div>
45 * <strong class="example">Example 3:
46 * <div class="example-block">
47 * Input: <span class="example-io">n = 4, edges = [[0,1],[1,2],[1,3]], x = 1, y = 3, z = 0</span>
48 * Output: <span class="example-io">1</span>
49 * Explanation:
50 * For each node, we compute its distances to nodes x = 1, y = 3, and z = 0.
51 * 
52 * 	Node 0 has distances 1, 2, and 0. After sorting, the distances are 0, 1, and 2, which do not satisfy the Pythagorean condition.
53 * 	Node 1 has distances 0, 1, and 1. After sorting, the distances are 0, 1, and 1. Since 0^2 + 1^2 = 1^2, node 1 is special.
54 * 	Node 2 has distances 1, 2, and 2. After sorting, the distances are 1, 2, and 2, which do not satisfy the Pythagorean condition.
55 * 	Node 3 has distances 1, 0, and 2. After sorting, the distances are 0, 1, and 2, which do not satisfy the Pythagorean condition.
56 * 
57 * Therefore, the answer is 1.
58 * </div>
59 *  
60 * Constraints:
61 * 
62 * 	4 <= n <= 10^5
63 * 	edges.length == n - 1
64 * 	edges[i] = [ui, vi]
65 * 	0 <= ui, vi, x, y, z <= n - 1
66 * 	x, y, and z are pairwise distinct.
67 * 	The input is generated such that edges represent a valid tree.
68 * 
69 */
70pub struct Solution {}
71
72// problem: https://leetcode.com/problems/pythagorean-distance-nodes-in-a-tree/
73// discuss: https://leetcode.com/problems/pythagorean-distance-nodes-in-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
74
75// submission codes start here
76
77impl Solution {
78    pub fn special_nodes(n: i32, edges: Vec<Vec<i32>>, x: i32, y: i32, z: i32) -> i32 {
79        0
80    }
81}
82
83// submission codes end
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88
89    #[test]
90    fn test_3820() {
91    }
92}
93