2025-09-13：最长特殊路径Ⅱ。用go语言，有一棵以 0 为根的无向树，节点编号为 0 到 n-1，边集合用长度为 n-1 的数组 edges 给出，其中每项 edges[i] = [u_i, v_i, len_i] 表示 u_i 与 v_i 之间有条权重为 len_i 的边。每个节点 i 还对应一个值 nums[i]。

把一条路径限定为从某个祖先节点沿着树一直走到它的某个后代（即沿根向下的方向）。如果这条路径上的节点值满足：除了至多一种数值可以出现两次以外，路径上所有节点的值互不相同，则称该路径为“特殊路径”。对任意特殊路径，其长度按路径上所有边权之和计算，节点数为路径上包含的节点个数。

要求返回一个长度为 2 的数组 result，其中：

• result[0] 表示所有特殊路径中能达到的最大总边长；

• result[1] 表示在那些具有最大总边长的特殊路径中，节点数最少的那个路径的节点数。

2 <= n <= 5 * 10000。

edges.length == n - 1。

edges[i].length == 3。

0 <= ui, vi < n。

1 <= lengthi <= 1000。

nums.length == n。

0 <= nums[i] <= 5 * 10000。

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

输入： edges = [[0,1,1],[1,2,3],[1,3,1],[2,4,6],[4,7,2],[3,5,2],[3,6,5],[6,8,3]], nums = [1,1,0,3,1,2,1,1,0]。

输出： [9,3]。

解释：

在下图中，节点的颜色代表它们在 nums 中的对应值。

最长的特殊路径是 1 -> 2 -> 4 和 1 -> 3 -> 6 -> 8，两者的长度都是 9。所有最长特殊路径中最小的节点数是 3 。

题目来自力扣3486。

我们来逐步分析这个问题和给定的代码实现：

代码思路（DFS遍历）

1. 构建图结构：使用邻接表表示树，每个节点存储其邻居及边权重。
2. 全局变量：
   • maxLen：记录当前找到的最大路径长度（边权和）。
   • minNodes：记录对应最大路径长度下的最小节点数。
   • dis：一个切片，记录从根节点到当前节点的累计距离（边权和）。初始为[0]（根节点距离为0）。
   • lastDepth：一个映射，记录每种颜色最近一次出现的深度（在dis切片中的索引位置，即深度索引）。注意：这里存储的是深度索引+1（即实际深度索引+1），所以下面使用时不需要再+1。
3. DFS递归函数：
   • 参数：当前节点x，父节点fa，topDepth（当前路径的窗口左边界，即路径起始深度索引），last1（维护的另一个边界，用于处理颜色重复的情况）。
   • 过程：
     a. 获取当前节点的颜色color。
     b. 从lastDepth中取出该颜色上次出现的深度索引（+1后的值）last2。
     c. 更新topDepth：取topDepth和min(last1, last2)的最大值。这里topDepth是当前路径的起始深度索引（即路径开始的位置），而last1和last2是用于限制路径起始位置以保持颜色约束（最多一种颜色出现两次）的关键。
     d. 计算当前路径的长度：dis[len(dis)-1] - dis[topDepth]（即从深度topDepth到当前节点的累计距离差）。
     e. 计算当前路径的节点数：len(dis) - topDepth。
     f. 如果当前路径长度大于maxLen，或者长度相等但节点数更少，则更新maxLen和minNodes。
     g. 记录当前颜色出现的深度（当前深度索引+1）到lastDepth[color]（即len(dis)）。
     h. 遍历邻居节点（排除父节点）：
     - 将邻居节点的累计距离（当前累计距离+边权）加入dis切片。
     - 递归调用DFS，传递参数：邻居节点、当前节点为父节点、更新后的topDepth、以及max(last1, last2)作为新的last1。
     - 回溯：从dis切片中弹出最后一项（恢复状态）。
     i. 回溯：恢复lastDepth[color]为原来的值last2。
4. 启动DFS：从根节点0开始，初始topDepth=0，last1=0。
5. 返回结果：[maxLen, minNodes]。

关键点解释

• 颜色约束处理：路径上最多一种颜色出现两次。通过lastDepth记录每种颜色最近出现的深度（索引+1），当再次遇到相同颜色时，需要调整路径起始位置（topDepth）以确保该颜色最多出现两次（实际上，如果同一种颜色出现两次，那么路径起始位置必须在这两次出现之间调整，以排除更早的重复颜色）。
• topDepth更新：取原topDepth和min(last1, last2)的最大值。这里last1和last2分别代表两种可能限制路径起始位置的边界（由于颜色重复），取最小值然后和原topDepth取最大，确保路径起始位置足够靠后以满足颜色约束。
• last1传递：在递归时，last1被更新为max(last1, last2)，表示传递一个更严格的边界（因为路径上可能已有颜色重复，需要限制后续路径的起始位置）。
• 累计距离：dis切片记录从根节点到当前节点的累计距离（边权和），通过差分计算路径长度。
• 节点数计算：路径节点数 = 当前深度索引 - 起始深度索引（topDepth） + 1？但代码中直接使用len(dis) - topDepth（因为dis的长度即当前深度索引+1，而topDepth是起始深度索引，所以节点数=(len(dis)-1) - topDepth + 1 = len(dis) - topDepth）正确。

时间复杂度

• 每个节点被访问一次，每次访问中遍历其所有邻居（边）。
• 每个节点处理中，对lastDepth的操作为O(1)（假设哈希表操作平均为O(1)）。
• 总时间复杂度为O(n)，即线性。

空间复杂度

• 图存储：O(n)（邻接表）。
• dis切片：深度最大为树高，最坏情况O(n)（链状树）。
• lastDepth映射：O(n)（存储n种颜色？但颜色值范围可能很大，但实际出现次数最多n种）。
• 递归栈深度：最坏O(n)（链状树）。
• 总空间复杂度为O(n)。

总结

该算法通过DFS遍历树，利用lastDepth映射记录颜色出现的深度，动态调整路径起始位置（topDepth）以满足颜色约束（最多一种颜色出现两次）。同时维护累计距离切片dis来计算路径长度和节点数。整个过程每个节点处理一次，总时间复杂度和空间复杂度均为O(n)。

对于给定的输入，输出为[9,3]，符合预期（最长路径长度为9，节点数最少为3）。

Go完整代码如下：

package main

import (
	"fmt"
)

func longestSpecialPath(edges [][]int, nums []int) []int {
	type edge struct{ to, weight int }
	g := make([][]edge, len(nums))
	for _, e := range edges {
		x, y, w := e[0], e[1], e[2]
		g[x] = append(g[x], edge{y, w})
		g[y] = append(g[y], edge{x, w})
	}

	maxLen := -1
	minNodes := 0
	dis := []int{0}
	// 颜色 -> 该颜色最近一次出现的深度 +1，注意这里已经 +1 了，下面不需要再 +1
	lastDepth := map[int]int{}

	var dfs func(int, int, int, int)
	dfs = func(x, fa, topDepth, last1 int) {
		color := nums[x]
		last2 := lastDepth[color]
		topDepth = max(topDepth, min(last1, last2)) // 相较 3425 题，维护窗口左端点的逻辑变了

		length := dis[len(dis)-1] - dis[topDepth]
		nodes := len(dis) - topDepth
		if length > maxLen || length == maxLen && nodes < minNodes {
			maxLen = length
			minNodes = nodes
		}

		lastDepth[color] = len(dis)
		for _, e := range g[x] {
			y := e.to
			if y != fa {
				dis = append(dis, dis[len(dis)-1]+e.weight)
				dfs(y, x, topDepth, max(last1, last2)) // 相较 3425 题，额外维护 last1
				dis = dis[:len(dis)-1]
			}
		}
		lastDepth[color] = last2
	}

	dfs(0, -1, 0, 0)
	return []int{maxLen, minNodes}
}

func main() {
	edges := [][]int{{0, 1, 1}, {1, 2, 3}, {1, 3, 1}, {2, 4, 6}, {4, 7, 2}, {3, 5, 2}, {3, 6, 5}, {6, 8, 3}}
	nums := []int{1, 1, 0, 3, 1, 2, 1, 1, 0}
	result := longestSpecialPath(edges, nums)
	fmt.Println(result)
}

Python完整代码如下：

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

import sys
sys.setrecursionlimit(10**7)

def longestSpecialPath(edges, nums):
    n = len(nums)
    g = [[] for _ in range(n)]
    for x, y, w in edges:
        g[x].append((y, w))
        g[y].append((x, w))

    maxLen = -1
    minNodes = 0
    dis = [0]  # 前缀距离，dis[i] 表示从根到当前路径上第 i 个位置（0 起）的距离
    lastDepth = {}  # 颜色 -> 最近一次出现的深度索引（len(dis) 时的值），缺省视为 0

    def dfs(x, fa, topDepth, last1):
        nonlocal maxLen, minNodes
        color = nums[x]
        last2 = lastDepth.get(color, 0)
        topDepth = max(topDepth, min(last1, last2))

        length = dis[-1] - dis[topDepth]
        nodes = len(dis) - topDepth
        if length > maxLen or (length == maxLen and nodes < minNodes):
            maxLen = length
            minNodes = nodes

        # 记录当前颜色的最近出现位置
        lastDepth[color] = len(dis)
        for y, w in g[x]:
            if y == fa:
                continue
            dis.append(dis[-1] + w)
            dfs(y, x, topDepth, max(last1, last2))
            dis.pop()
        # 恢复之前的状态
        if last2 == 0:
            lastDepth.pop(color, None)
        else:
            lastDepth[color] = last2

    dfs(0, -1, 0, 0)
    return [maxLen, minNodes]

if __name__ == "__main__":
    edges = [[0,1,1],[1,2,3],[1,3,1],[2,4,6],[4,7,2],[3,5,2],[3,6,5],[6,8,3]]
    nums = [1,1,0,3,1,2,1,1,0]
    print(longestSpecialPath(edges, nums))