Count Tree Vertices with Pythagorean Distances

Problem Statement

You are given an undirected, unweighted tree with n vertices numbered from 1 to n, represented by an edge list edges of length n - 1. You are also given three distinct target vertices x, y, and z.

A vertex v is called a Pythagorean vertex if:

1. The distances from v to x, y, and z are all strictly positive integers (that is, v != x, v != y, and v != z).
2. Let these distances, sorted in non-decreasing order, be a, b, and c such that a <= b <= c. Then, a^2 + b^2 = c^2.

Return the total number of Pythagorean vertices in the tree.

Function Signature

def count_pythagorean_vertices(n: int, edges: list[list[int]], x: int, y: int, z: int) -> int:
    pass

Input & Output Format

• Input:
  • n: an integer representing the number of vertices.
  • edges: a list of length n - 1 where each element is a pair [u, v] indicating an undirected edge between u and v.
  • x, y, z: three distinct integers in the range [1, n].
• Output:
  • An integer representing the count of valid Pythagorean vertices.

Constraints

• 3 <= n <= 10^5
• edges.length == n - 1
• 1 <= edges[i][0], edges[i][1] <= n
• The input graph is guaranteed to be a valid connected tree.
• 1 <= x, y, z <= n, and x, y, z are pairwise distinct.

Examples

Example 1

Input:
n = 8
edges = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [3, 7], [7, 8]]
x = 4
y = 8
z = 6

Output: 1
Explanation:
Evaluate vertex 1:
- dist(1, x) = dist(1, 4) = 3 (path: 1-2-3-4)
- dist(1, y) = dist(1, 8) = 4 (path: 1-2-3-7-8)
- dist(1, z) = dist(1, 6) = 5 (path: 1-2-3-4-5-6)
Sorted distances are [3, 4, 5]. Since 3^2 + 4^2 = 9 + 16 = 25 = 5^2, vertex 1 is a Pythagorean vertex.
No other vertex in the tree satisfies the condition.

Example 2

Input:
n = 4
edges = [[1, 2], [2, 3], [3, 4]]
x = 1
y = 2
z = 3

Output: 0
Explanation:
The only candidate node is 4. Its distances to x, y, and z are 3, 2, and 1. Sorted: [1, 2, 3].
1^2 + 2^2 = 5 != 9 = 3^2, so vertex 4 is not a Pythagorean vertex.

Edge Cases

• Trees with fewer than 13 nodes can still contain valid Pythagorean vertices if paths overlap.
• Target vertices x, y, and z must be excluded since one of their distances would be 0 (distances must be strictly positive).
• Deep linear trees (linked list structure) where recursion could hit the call stack limit if DFS is not written iteratively.