2026-11-04：树的加权和。用go语言，现有一棵含 n 个结点的有根树，结点编号从 0 到 n-1，根结点为 0。数组 parent 描述父子关系：parent

2026-11-04：树的加权和。用go语言，现有一棵含 n 个结点的有根树，结点编号从 0 到 n-1，根结点为 0。数组 parent 描述父子关系：parent[0] 为 -1，对于其余结点 i，parent[i] 是结点 i 的父结点编号。另有一个长度相同的数组 nums，其中 nums[i] 是结点 i 的数值。

规定根结点所在层数为 1，某个结点的深度等于从根到它经过的结点个数。整棵树的高度 h 等于所有结点深度的最大值。对于深度为 d 的结点 i，其权重按 nums[i] 乘以 (h – d + 1) 计算。要求计算所有结点权重相加后的总和。

1 <= n <= 100000。

n == parent.length == nums.length。

parent[0] == -1。

对于所有 i，其中 i 位于 [1, n – 1]，均有 0 <= parent[i] <= n – 1。

1 <= nums[i] <= 1000000。

保证输入数组 parent 表示一棵以节点 0 为根节点的有效树。

在这里插入图片描述

输入： parent = [-1,0,0,0,2,2], nums = [5,2,3,1,4,6]。

输出： 37。

解释：

该树的高度为 3。

节点

nums[i]

深度（d）

权重

0

5

1

5 * (3 – 1 + 1) = 15

1

2

2

2 * (3 – 2 + 1) = 4

2

3

2

3 * (3 – 2 + 1) = 6

3

1

2

1 * (3 – 2 + 1) = 2

4

4

3

4 * (3 – 3 + 1) = 4

5

6

3

6 * (3 – 3 + 1) = 6

所有节点的权重之和为 15 + 4 + 6 + 2 + 4 + 6 = 37。

题目来自力扣4015。

大体步骤如下：

1.确定结点数量并准备树的存储结构

• 读取parent数组，其长度就是树的结点数n。

• 创建一个长度为n的邻接表，用来存放每个结点的所有子结点。

• 因为题目保证parent[0] = -1，且其余结点都只有一个父结点，所以从下标1开始遍历每个结点i：

• 找到它的父结点parent[i]；

• 把结点i加入到父结点的子结点列表中。

• 完成后，就得到了从根结点0出发的完整有根树结构。

2.准备记录每个结点深度的数组

• 创建一个长度为n的depth数组。

• 根据代码中的定义，根结点0的深度记为0。

• 这里的“深度”表示从根结点到当前结点经过的边数，因此：

• 根结点深度为0；

• 根结点的直接子结点深度为1；

• 再往下一层深度为2，依此类推。

• 这个深度与题目中“根所在层数为 1”的定义相差 1，后面计算权重时会自然抵消。

3.通过深度优先搜索计算每个结点的深度，并求整棵树的高度

• 从根结点0开始进行深度优先搜索。

• 搜索函数的作用有两个：

• 在访问子结点时，设置子结点的深度为当前结点深度加 1；

• 返回以当前结点为根的子树高度，这里的“高度”按结点个数计算。

• 对于当前结点，初始记录一个局部最大高度为0。

• 遍历当前结点的每个子结点：

• 先令子结点的深度等于当前结点深度加 1；

• 再递归计算子结点所在子树的高度；

• 用子树的返回值更新当前结点的局部最大高度。

• 当前结点处理完所有子结点后，返回“局部最大高度 + 1”。

• 如果是叶子结点，没有子结点，局部最大高度为0，返回1，表示该叶子自身形成的高度为 1；

• 如果某个结点下面还有子树，则返回从该结点到最深叶子经过的结点个数。

• 从根结点调用搜索后，得到的返回值就是整棵树的高度h。

• 在示例中，整棵树的高度为3。

4.理解代码中深度与题目中层数的对应关系

• 代码中根结点深度depth[0] = 0。

• 题目中根结点层数d = 1。

• 对任意结点，有：

• 题目层数d = depth[i] + 1。

• 题目要求的权重是：

•nums[i] * (h - d + 1)。

• 将d = depth[i] + 1代入：

•h - d + 1 = h - (depth[i] + 1) + 1 = h - depth[i]。

• 所以代码中直接用nums[i] * (h - depth[i])计算权重，与题目公式完全一致。

5.遍历所有结点，累加加权和

• 准备好一个 64 位整数变量保存总和，避免结果溢出。

• 遍历每个结点i和它的数值nums[i]：

• 根据已经得到的整棵树高度h；

• 根据该结点的代码深度depth[i]；

• 计算该结点的权重：nums[i] * (h - depth[i])；

• 将该权重累加到总和中。

• 示例中各结点情况为：

• 结点 0：深度 0，权重5 * (3 - 0) = 15；

• 结点 1：深度 1，权重2 * (3 - 1) = 4；

• 结点 2：深度 1，权重3 * (3 - 1) = 6；

• 结点 3：深度 1，权重1 * (3 - 1) = 2；

• 结点 4：深度 2，权重4 * (3 - 2) = 4；

• 结点 5：深度 2，权重6 * (3 - 2) = 6。

• 总和为：

•15 + 4 + 6 + 2 + 4 + 6 = 37。

6.返回并输出结果

• 遍历完成后，累加变量中保存的就是所有结点权重之和。

• 示例最终输出37。

时间复杂度分析：

• 建树需要遍历parent中除根结点外的所有结点，共O(n)。

• 深度优先搜索会访问每个结点一次，并处理每条父子边一次，共O(n)。

• 最后遍历nums累加权重，共O(n)。

• 因此总时间复杂度为O(n)。

额外空间复杂度分析：

• 邻接表需要存储所有子结点关系，空间为O(n)。

•depth数组长度为n，空间为O(n)。

• 深度优先搜索使用递归调用栈，最坏情况下树退化成链，递归深度为O(n)；最好或平均情况下与树高有关。

• 因此总的最坏额外空间复杂度为O(n)。

Go完整代码如下：

package main

 import (
    "fmt"
)

 func weightedSum(parent []int, nums []int) (ans int64) {
    n := len(parent)
    g := make([][]int, n)
    for i := 1; i < n; i++ {
        p := parent[i]
        g[p] = append(g[p], i)
    }

     depth := make([]int, n)
    var dfs func(int)int
    dfs = func(x int) (h int) {
        for _, y := range g[x] {
            depth[y] = depth[x] + 1
            h = max(h, dfs(y))
        }
        return h + 1
    }
    h := dfs(0)

     for i, x := range nums {
        ans += int64(x) * int64(h-depth[i])
    }
    return
}

 func main() {
    parent := []int{-1, 0, 0, 0, 2, 2}
    nums := []int{5, 2, 3, 1, 4, 6}
    result := weightedSum(parent, nums)
    fmt.Println(result)
}

Python完整代码如下：

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

 def weighted_sum(parent, nums):
    n = len(parent)
    g = [[] for _ in range(n)]

     for i in range(1, n):
        p = parent[i]
        g[p].append(i)

     depth = [0] * n

     def dfs(x):
        h = 0
        for y in g[x]:
            depth[y] = depth[x] + 1
            h = max(h, dfs(y))
        return h + 1

     h = dfs(0)

     ans = 0
    for i, x in enumerate(nums):
        ans += x * (h - depth[i])

     return ans

 if __name__ == "__main__":
    parent = [-1, 0, 0, 0, 2, 2]
    nums = [5, 2, 3, 1, 4, 6]
    result = weighted_sum(parent, nums)
    print(result)

C++完整代码如下：

  

  

  

  


 using namespace std;

 long long weightedSum(const vector& parent, const vector& nums) {
    int n = parent.size();
    vector 
 
 int 
 >> g(n); 
 
 
 
 
      
 for 
  ( 
 int 
  i =  
 1 
 ; i < n; ++i) { 
 
 
          
 int 
  p = parent[i]; 
 
 
         g[p].push_back(i); 
 
 
     } 
 
 
 
 
     vector< 
 int 
 > depth(n,  
 0 
 ); 
 
 
 
 
     function< 
 int 
 ( 
 int 
 )> dfs = [&]( 
 int 
  x) ->  
 int 
  { 
 
 
          
 int 
  h =  
 0 
 ; 
 
 
          
 for 
  ( 
 int 
  y : g[x]) { 
 
 
             depth[y] = depth[x] +  
 1 
 ; 
 
 
             h = max(h, dfs(y)); 
 
 
         } 
 
 
          
 return 
  h +  
 1 
 ; 
 
 
     }; 
 
 
 
 
      
 int 
  h = dfs( 
 0 
 ); 
 
 
 
 
     long long ans =  
 0 
 ; 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < n; ++i) { 
 
 
         ans +=  
 1 
 LL * nums[i] * (h - depth[i]); 
 
 
     } 
 
 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector< 
 int 
 > parent = { 
 -1 
 ,  
 0 
 ,  
 0 
 ,  
 0 
 ,  
 2 
 ,  
 2 
 }; 
 
 
     vector< 
 int 
 > nums = { 
 5 
 ,  
 2 
 ,  
 3 
 ,  
 1 
 ,  
 4 
 ,  
 6 
 }; 
 
 
 
 
     long long result = weightedSum(parent, nums); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。