摘要：2025-09-13：最长特殊路径Ⅱ。用go语言，有一棵以 0 为根的无向树，节点编号为 0 到 n-1，边集合用长度为 n-1 的数组 edges 给出，其中每项 edges[i] = [u_i, v_i, len_i] 表示 u_i 与 v_i 之间有条权
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
edges.length == n - 1。
edges[i].length == 3。
0
1
nums.length == n。
0
输入保证 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。
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）。
package mainimport ( "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我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。
·
来源：小贝课堂
