2026-09-23：任务完成时间Ⅰ。用go语言，有 n 个任务，编号从 0 到 n-1，它们组成一棵以任务 0 为根的树。edges 中每个二元组表示前一个

2026-09-23：任务完成时间Ⅰ。用go语言，有 n 个任务，编号从 0 到 n-1，它们组成一棵以任务 0 为根的树。edges 中每个二元组表示前一个任务是后一个任务的直接上级。baseTime[i] 表示处理任务 i 本身需要的基础时长。
一个任务的最终完成时刻这样计算：如果它没有下级任务，那么它的完成时刻就等于 baseTime[i]。如果它有下级任务，就先从所有直接下级的完成时刻中找出最小值 earliest 和最大值 latest。用 latest 减 earliest，再加上这个任务自身的 baseTime[i]，得到该任务自身持续的时间。然后把这个自身持续时间加到 latest 上，得到该任务的完成时刻。

最后需要返回根任务 0 的完成时刻。

1 <= n <= 100000。

edges.length = n – 1。

edges[i] == [ui, vi]。

0 <= ui, vi <= n – 1。

ui != vi。

输入保证 edges 表示一棵有效的树。

baseTime.length == n。

1 <= baseTime[i] <= 100000。

每个任务的完成时间保证小于 2⁵³。

输入： n = 4, edges = [[0,1],[0,2],[2,3]], baseTime = [5,8,2,1]。

输出： 18。

解释：

任务 1 是叶子节点，因此其完成时间为 baseTime[1] = 8。

任务 3 是叶子节点，因此其完成时间为 baseTime[3] = 1。

任务 2 有一个子任务 3：

earliest = latest = 1

ownDuration = (latest – earliest) + baseTime[2] = 0 + 2 = 2

任务 2 的完成时间为 latest + ownDuration = 1 + 2 = 3

任务 0 有两个子任务，完成时间分别为 8 和 3：

earliest = 3, latest = 8

ownDuration = (latest – earliest) + baseTime[0] = (8 – 3) + 5 = 10

任务 0 的完成时间为 latest + ownDuration = 8 + 10 = 18

题目来自力扣3965。

一、建立”上级 → 下级”的邻接表

代码先创建一个长度为n的切片g，g[i]用来存放任务i的所有直接下级的编号。

然后遍历edges里每一条[x, y]：题目保证x是y的直接上级，所以直接把y追加进g[x]即可，不需要像无向图那样双向加边。

因为题目给定edges.length = n - 1，这一步总共追加n - 1次，最终g里恰好存了n - 1条父子关系。此时如果某个g[x]仍然是空的（nil），就说明任务x没有任何下级，也就是叶子。

二、从根节点 0 出发做后序遍历（DFS）

定义一个递归函数dfs(x)，它的语义非常明确：返回任务x的最终完成时刻。

之所以必须是”后序”（先子树、后自身），是因为一个任务的完成时刻完全由它所有下级的完成时刻决定——你不先把子树的结果算出来，当前节点就无从下手。而递归天然就是后序的：进入x后先把每个子节点递归到底，回到x时才做合并。

由于题目保证这是一棵以 0 为根的有效树，从 0 出发的 DFS 一定能不重不漏地覆盖全部n个节点，不需要 visited 数组，也不会有环。

三、叶子节点的处理

dfs(x)一进来先判断g[x] == nil。

• 如果成立，说明x没有下级任务，按题目规则它的完成时刻就等于baseTime[x]，直接返回。

• 这里有个顺带的好处：当n = 1时，根节点 0 本身就是叶子，同样走这个分支返回baseTime[0]，不需要额外特判。

四、非叶子节点：收集 earliest 与 latest

对于有下级的节点x，遍历g[x]里的每一个下级y，递归拿到t = dfs(y)，然后维护两个量：

•earliest：所有t中的最小值，初始化为math.MaxInt（一个足够大的哨兵，保证第一个t一定能把它替换掉）。

•latest：所有t中的最大值，初始化为0。这里初值取 0 是安全的，因为baseTime[i] >= 1，任何任务的完成时刻都必然是正数，第一个t一定大于 0。

遍历完所有子节点后，earliest和latest就分别是”最快收尾的下级时刻”和”最慢收尾的下级时刻”。

五、合并公式（核心一步）

按题意，节点x自身的持续时间是：

ownDuration = (latest - earliest) + baseTime[x]

而x的完成时刻是：

latest + ownDuration = latest + (latest - earliest) + baseTime[x]
                     = 2 × latest - earliest + baseTime[x]

代码里直接写成了latest*2 - earliest + baseTime[x]，只是把上面的式子合并化简、省掉了中间变量，本质与题目描述完全一致。

可以这样直觉理解：所有下级任务是并行推进的，最慢的那个要到latest时刻才收尾；而x自身的处理需要占掉一段时长，这段时长由两部分构成——(latest - earliest)是等待各下级”对齐”所产生的空档期，baseTime[x]是自身的基础处理时长；并且这段自身处理被安排在latest之后串行执行，所以总完成时刻是latest + ownDuration。

关于数值安全：题目保证最终结果小于 2⁵³，而 Go 在 64 位平台上int本身就是 64 位，中间用int累加不会溢出，最后再转成int64返回。

六、返回根任务的结果

main里调用dfs(0)，得到的就是整棵树的最终完成时刻，转成int64后返回。

七、跟着样例走一遍

树形结构：0 → {1, 2}，2 → {3}，baseTime = [5, 8, 2, 1]。

调用

情况

计算

返回

dfs(1)

叶子

直接取baseTime[1]

8dfs(3)

叶子

直接取baseTime[3]

1dfs(2)

只有下级 3

t = 1

，故earliest = latest = 1；1×2 − 1 + 2

3dfs(0)

下级 1 给 8，下级 2 给 3

earliest = 3

，latest = 8；8×2 − 3 + 5 = 16 − 3 + 5

18

最终输出18，与题目给的答案一致。

八、复杂度分析

总时间复杂度：O(n)

• 建邻接表：遍历n - 1条边，每边一次追加，O(n)。

• DFS：每个节点恰好进入一次（O(n) 次调用），每条父子关系恰好被遍历一次（O(n − 1) 次），每次操作都是常数时间。

• 两部分相加仍是 O(n)，且这是下界——你必须至少看完全部n个节点和n − 1条边才能作答。

总额外空间复杂度：O(n)

（这里不计入输入edges和baseTime本身占用的空间。）

• 邻接表g：n个切片头 +n − 1个存储的子节点编号，合计 O(n)。

• 递归调用栈：深度等于树高。最坏情况是退化成一条链，深度达到n，即 O(n)；最理想（树较平衡）时为 O(log n)。严格来说这部分的量级是O(树高)，其上界为 O(n)。

• 没有 visited 数组、没有队列等其它辅助结构。

因此总体额外空间由邻接表和递归栈共同决定，上界为O(n)。

补充一点工程上的安心：n 最大到 10⁵，最坏递归深度也是 10⁵。Go 的 goroutine 栈会自动动态增长（上限很高），所以这种深度的递归不会像某些固定栈语言那样爆栈。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
)

 func finishTime(n int, edges [][]int, baseTime []int)int64 {
    g := make([][]int, n)
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y) // 题目保证 x 是 y 的父节点
    }

     var dfs func(int)int
    dfs = func(x int)int {
        if g[x] == nil { // x 是叶子
            return baseTime[x]
        }
        earliest, latest := math.MaxInt, 0
        for _, y := range g[x] {
            t := dfs(y)
            earliest = min(earliest, t)
            latest = max(latest, t)
        }
        return latest*2 - earliest + baseTime[x]
    }

     returnint64(dfs(0))
}

 func main() {
    n := 4
    edges := [][]int{{0, 1}, {0, 2}, {2, 3}}
    baseTime := []int{5, 8, 2, 1}
    result := finishTime(n, edges, baseTime)
    fmt.Println(result)
}

Python完整代码如下：

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

 import sys
from typing import List

 def finishTime(n: int, edges: List[List[int]], baseTime: List[int]) -> int:
    sys.setrecursionlimit(1000000)

     g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)  # u 是 v 的父节点

     def dfs(x: int) -> int:
        if not g[x]:  # 叶子节点
            return baseTime[x]

         earliest = float('inf')
        latest = 0

         for y in g[x]:
            t = dfs(y)
            earliest = min(earliest, t)
            latest = max(latest, t)

         return latest * 2 - earliest + baseTime[x]

     return dfs(0)

 if __name__ == "__main__":
    n = 4
    edges = [[0, 1], [0, 2], [2, 3]]
    baseTime = [5, 8, 2, 1]

     result = finishTime(n, edges, baseTime)
    print(result)

C++完整代码如下：

  

  

    

  


 using namespace std;

 long long finishTime(int n, vector 
 
 int 
 >>& edges, vector< 
 int 
 >& baseTime) { 
 
 
     vector 
 
 int 
 >> g(n); 
 
 
      
 for 
  ( 
 const 
  auto& e : edges) { 
 
 
          
 int 
  x = e[ 
 0 
 ], y = e[ 
 1 
 ]; 
 
 
         g[x].push_back(y);  
 // 题目保证 x 是 y 的父节点 
 
 
     } 
 
 
 
 
     function 
 
 int 
 )> dfs = [&]( 
 int 
  x) -> long long { 
 
 
          
 if 
  (g[x].empty()) {  
 // x 是叶子节点 
 
 
              
 return 
  baseTime[x]; 
 
 
         } 
 
 
 
 
         long long earliest = LLONG_MAX; 
 
 
         long long latest =  
 0 
 ; 
 
 
 
 
          
 for 
  ( 
 int 
  y : g[x]) { 
 
 
             long long t = dfs(y); 
 
 
             earliest = min(earliest, t); 
 
 
             latest = max(latest, t); 
 
 
         } 
 
 
 
 
          
 return 
  latest *  
 2 
  - earliest + baseTime[x]; 
 
 
     }; 
 
 
 
 
      
 return 
  dfs( 
 0 
 ); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
      
 int 
  n =  
 4 
 ; 
 
 
     vector 
 
 int 
 >> edges = {{ 
 0 
 ,  
 1 
 }, { 
 0 
 ,  
 2 
 }, { 
 2 
 ,  
 3 
 }}; 
 
 
     vector< 
 int 
 > baseTime = { 
 5 
 ,  
 8 
 ,  
 2 
 ,  
 1 
 }; 
 
 
 
 
     long long result = finishTime(n, edges, baseTime); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 
 
 
 

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