Count Pythagorean Distance Nodes in a Tree

### Problem You are given an undirected tree with `n` nodes numbered `0..n-1`, its `n-1` edges, and three pairwise distinct target nodes `x`, `y`, and `z`. Distance is the number of edges on the unique path between two nodes. For each node `u`, consider its three distances to the targets. Write those distances in non-decreasing order as `a <= b <= c`. Count `u` as special exactly when: ```text a^2 + b^2 = c^2 ``` Return the number of special nodes. Zero distances and equal distances are permitted: for example, `(0,d,d)` satisfies the equation. No additional positive-length or non-degenerate-triangle requirement applies. ```cpp class Solution { public: int specialNodes(int n, vector<vector<int>>& edges, int x, int y, int z); }; ``` ### Examples **Example 1:** ```text Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]], x = 0, y = 2, z = 4 Output: 1 Explanation: Node 2 has distances (2,0,2), whose ordered values satisfy 0^2+2^2 = 2^2. No other node satisfies the equation. ``` **Example 2:** ```text Input: n = 6, edges = [[0,1],[1,2],[2,3],[3,4],[4,5]], x = 3, y = 4, z = 5 Output: 2 Explanation: Node 0 has distances (3,4,5), and node 4 has distances (1,0,1). Both satisfy the equation after ordering. The other four nodes do not. ``` ### Constraints - `4 <= n <= 100000`. - `edges.length == n-1`, and each entry is an undirected pair `[u,v]`. - All edge endpoints and `x,y,z` lie in `0..n-1`. - `x`, `y`, and `z` are pairwise distinct. - `edges` represents a valid tree. ### Clarifying Questions - Can `u` be one of the target nodes? Yes; its distance to itself is zero. - Must all three distances be positive or different? No; use exactly the stated equation. - Is the distance measured in edges? Yes; edges have no weights. - Does a node count multiple times for different orderings? No; each special node contributes one. ### What a Strong Answer Covers - Exact distances to all three targets and the specified squared-distance equality. - Zero distances, repeated distances, and nodes that are themselves targets. - A completeness argument counting each qualifying node once. - Numeric safety and resource bounds, including a deep tree at maximum size. ### Follow-up Questions - What extra output would be needed to return the special node identifiers? - How would a weighted-edge version need to specify its distance units and numeric limits? ```hint Compute three complete distance arrays Run an iterative breadth-first search from each target. At each node, order its three distances and test the equation using wide arithmetic before multiplication. Keep the source's zero-distance cases; this is an integer equality test rather than a geometric triangle filter. ```