2026-05-28：树上的勾股距离节点。用go语言，给定一棵包含 n 个节点的无向树（节点编号为 0 到 n-1），树的边用长度为 n-1 的数组 edges 表示：edges[i] = [ui, vi] 表示 ui 与 vi 之间有一条无向边。再给定三个两两不同的目标节点 x、y、z。

对树中任意一个节点 u，分别计算它到 x、y、z 的距离，记为 dx、dy、dz。若将这三个距离中的数按从小到大排序后，得到的 (a, b, c) 满足 a² + b² = c²，则称该节点 u 为“特殊节点”。

要求统计树中所有特殊节点的个数，并返回该数量。

4 <= n <= 100000。

edges.length == n - 1。

edges[i] = [ui, vi]。

0 <= ui, vi, x, y, z <= n - 1。

x, y 和 z 互不相同。

输入生成的 edges 表示一棵有效的树。

输入： n = 4, edges = [[0,1],[0,2],[0,3]], x = 1, y = 2, z = 3。

输出： 3。

解释：

对于每个节点，我们计算它到节点 x = 1、y = 2 和 z = 3 的距离。

节点 0 的距离分别为 1, 1, 1。排序后，距离为 1, 1, 1，不满足勾股定理条件。

节点 1 的距离分别为 0, 2, 2。排序后，距离为 0, 2, 2。由于 02 + 22 = 22，节点 1 是特殊的。

节点 2 的距离分别为 2, 0, 2。排序后，距离为 0, 2, 2。由于 02 + 22 = 22，节点 2 是特殊的。

节点 3 的距离分别为 2, 2, 0。排序后，距离为 0, 2, 2。这也满足勾股定理条件。

因此，节点 1、2 和 3 是特殊节点，答案为 3。

题目来自力扣3820。

树上勾股距离节点解题步骤详解

第一步：构建无向树的邻接表存储结构

树是由节点和边组成的无向连通无环图，首先需要把输入的边信息转换成计算机容易遍历的存储结构——邻接表。

1. 已知总共有 n 个节点（编号 0~n-1），创建一个长度为 n 的列表，列表中每个位置对应一个节点，存储该节点直接相连的所有邻居节点。
2. 遍历输入的所有边（共 n-1 条），每一条边连接两个节点 v 和 w：
   • 把 w 添加到 v 的邻居列表中；
   • 把 v 添加到 w 的邻居列表中（因为是无向树，边是双向的）。
3. 最终得到完整的树的邻接表，后续所有距离计算都基于这个结构进行。

第二步：实现「单源最短距离计算」功能

树的特性：任意两个节点之间有且仅有一条唯一路径，因此从一个起点到所有其他节点的距离，就是路径上的边数，用深度优先遍历（DFS）就能一次性算出所有距离。
这个功能的核心作用是：输入一个起点节点，输出该起点到树上所有节点的距离数组。
具体执行步骤：

1. 创建一个长度为 n 的距离数组，初始值全为 0（数组下标对应节点编号，值对应距离）。
2. 从起点开始做深度优先遍历（DFS），遍历规则：
   • 记录当前遍历到的节点，以及它的「父节点」（避免走回头路）；
   • 遍历当前节点的所有邻居，跳过父节点（防止重复遍历）；
   • 邻居节点的距离 = 当前节点距离 + 1；
   • 递归遍历这个邻居节点，重复上述操作。
3. 遍历完成后，距离数组中就存储了起点到树上每一个节点的距离。

第三步：分别计算三个目标节点到全节点的距离

题目给定了三个固定节点 x、y、z，需要分别以这三个节点为起点，调用第二步的距离计算功能，得到三组距离数据：

1. 以 x 为起点，计算得到数组 dx：dx[i] 表示节点 i 到 x 的距离；
2. 以 y 为起点，计算得到数组 dy：dy[i] 表示节点 i 到 y 的距离；
3. 以 z 为起点，计算得到数组 dz：dz[i] 表示节点 i 到 z 的距离。
   至此，我们拿到了每个节点对应的三个距离值。

第四步：遍历所有节点，判断是否为「特殊节点」

逐个检查树上的每一个节点 i（从 0 到 n-1），判断规则严格按照题目要求：

1. 取出节点 i 的三个距离：dx[i]、dy[i]、dz[i]；
2. 对这三个数字从小到大排序，得到排序后的三个数 a、b、c（a ≤ b ≤ c）；
3. 验证勾股定理：判断 a² + b² 是否等于 c²；
4. 如果满足等式，该节点就是特殊节点，计数加 1；不满足则跳过。

第五步：返回最终统计结果

遍历完所有节点后，统计得到的总数量，就是题目要求的答案。

时间复杂度分析

我们按照步骤拆分计算复杂度（n 为节点总数）：

1. 构建邻接表：遍历 n-1 条边，复杂度为 O(n)；
2. 三次距离计算：每次DFS遍历整棵树，所有节点和边都访问一次，单次 O(n)，三次总复杂度 O(3n) = O(n)；
3. 节点判断与计数：遍历 n 个节点，每个节点仅做排序（3个数字排序是常数时间 O(1)）和简单计算，总复杂度 O(n)。

总时间复杂度：O(n)
（线性复杂度，适合题目要求的 n ≤ 100000 大数据量）

空间复杂度分析

统计程序运行过程中占用的额外空间：

1. 邻接表：存储 n 个节点和 n-1 条边，空间 O(n)；
2. 距离数组：一共创建 3 个长度为 n 的数组，空间 O(3n) = O(n)；
3. DFS递归栈：树的深度最坏为 n（链状树），递归栈空间 O(n)；
4. 其他变量（计数、临时数组）均为常数空间 O(1)。

总空间复杂度：O(n)

总结

1. 核心流程：建邻接表 → 三次DFS算距离 → 遍历节点验证勾股定理 → 统计结果；
2. 时间复杂度：O(n)（线性时间，高效处理十万级节点）；
3. 空间复杂度：O(n)（线性空间，符合题目内存要求）。

Go完整代码如下：

package main

import (
	"fmt"
	"slices"
)

func specialNodes(n int, edges [][]int, x, y, z int) (ans int) {
	g := make([][]int, n)
	for _, e := range edges {
		v, w := e[0], e[1]
		g[v] = append(g[v], w)
		g[w] = append(g[w], v)
	}

	calcDis := func(start int) []int {
		dis := make([]int, n)
		var dfs func(int, int)
		dfs = func(v, fa int) {
			for _, w := range g[v] {
				if w != fa {
					dis[w] = dis[v] + 1
					dfs(w, v)
				}
			}
		}
		dfs(start, -1)
		return dis
	}

	dx := calcDis(x)
	dy := calcDis(y)
	dz := calcDis(z)

	for i := range n {
		a := []int{dx[i], dy[i], dz[i]}
		slices.Sort(a)
		if a[0]*a[0]+a[1]*a[1] == a[2]*a[2] {
			ans++
		}
	}
	return
}

func main() {
	n := 4
	edges := [][]int{{0, 1}, {0, 2}, {0, 3}}
	x := 1
	y := 2
	z := 3
	result := specialNodes(n, edges, x, y, z)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def specialNodes(n: int, edges: List[List[int]], x: int, y: int, z: int) -> int:
    # 构建邻接表
    g = [[] for _ in range(n)]
    for v, w in edges:
        g[v].append(w)
        g[w].append(v)

    # 计算从 start 出发到所有节点的距离
    def calcDis(start: int) -> List[int]:
        dis = [0] * n
        visited = [False] * n
        
        def dfs(v: int):
            visited[v] = True
            for w in g[v]:
                if not visited[w]:
                    dis[w] = dis[v] + 1
                    dfs(w)
        
        dfs(start)
        return dis

    dx = calcDis(x)
    dy = calcDis(y)
    dz = calcDis(z)

    ans = 0
    for i in range(n):
        a = [dx[i], dy[i], dz[i]]
        a.sort()
        if a[0] * a[0] + a[1] * a[1] == a[2] * a[2]:
            ans += 1
    
    return ans


def main():
    n = 4
    edges = [[0, 1], [0, 2], [0, 3]]
    x = 1
    y = 2
    z = 3
    result = specialNodes(n, edges, x, y, z)
    print(result)


if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

int specialNodes(int n, vector<vector<int>>& edges, int x, int y, int z) {
    // 构建邻接表
    vector<vector<int>> g(n);
    for (auto& e : edges) {
        int v = e[0], w = e[1];
        g[v].push_back(w);
        g[w].push_back(v);
    }

    // 计算从 start 出发到所有节点的距离
    auto calcDis = [&](int start) -> vector<int> {
        vector<int> dis(n, 0);

        // DFS 函数声明
        function<void(int, int)> dfs = [&](int v, int fa) {
            for (int w : g[v]) {
                if (w != fa) {
                    dis[w] = dis[v] + 1;
                    dfs(w, v);
                }
            }
        };

        dfs(start, -1);
        return dis;
    };

    vector<int> dx = calcDis(x);
    vector<int> dy = calcDis(y);
    vector<int> dz = calcDis(z);

    int ans = 0;
    for (int i = 0; i < n; i++) {
        vector<int> a = {dx[i], dy[i], dz[i]};
        sort(a.begin(), a.end());
        if (a[0] * a[0] + a[1] * a[1] == a[2] * a[2]) {
            ans++;
        }
    }

    return ans;
}

int main() {
    int n = 4;
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {0, 3}};
    int x = 1, y = 2, z = 3;

    int result = specialNodes(n, edges, x, y, z);
    cout << result << endl;

    return 0;
}