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.
You are also given three distinct target nodes x, y, and z.
For any node u in the tree:
dx be the distance from u to node xdy be the distance from u to node ydz be the distance from u to node zThe node u is called special if the three distances form a Pythagorean Triplet.
Return an integer denoting the number of special nodes in the tree.
A Pythagorean triplet consists of three integers a, b, and c which, when sorted in ascending order, satisfy a2 + b2 = c2.
The distance between two nodes in a tree is the number of edges on the unique path between them.
Example 1:
Input: n = 4, edges = [[0,1],[0,2],[0,3]], x = 1, y = 2, z = 3
Output: 3
Explanation:
For each node, we compute its distances to nodes x = 1, y = 2, and z = 3.
02 + 22 = 22, node 1 is special.02 + 22 = 22, node 2 is special.Therefore, nodes 1, 2, and 3 are special, and the answer is 3.
Example 2:
Input: n = 4, edges = [[0,1],[1,2],[2,3]], x = 0, y = 3, z = 2
Output: 0
Explanation:
For each node, we compute its distances to nodes x = 0, y = 3, and z = 2.
No node satisfies the Pythagorean condition. Therefore, the answer is 0.
Example 3:
Input: n = 4, edges = [[0,1],[1,2],[1,3]], x = 1, y = 3, z = 0
Output: 1
Explanation:
For each node, we compute its distances to nodes x = 1, y = 3, and z = 0.
02 + 12 = 12, node 1 is special.Therefore, the answer is 1.
Constraints:
4 <= n <= 105edges.length == n - 1edges[i] = [ui, vi]0 <= ui, vi, x, y, z <= n - 1x, y, and z are pairwise distinct.edges represent a valid tree.Solutions for this problem are being prepared.
Try solving it yourselfPractice Pythagorean Distance Nodes in a Tree with our built-in code editor and test cases.
Practice on FleetCode