3486. 最长特殊路径 II

Hard

题目描述

给你一个以节点 0 为根的无向树，有 n 个节点，编号从 0 到 n - 1。这通过一个长度为 n - 1 的二维数组 edges 表示，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和 vi 之间有一条长度为 lengthi 的边。同时给你一个整数数组 nums，其中 nums[i] 表示节点 i 的值。

特殊路径定义为从祖先节点到后代节点的向下路径，其中所有节点值都是不同的，除了最多有一个值可能出现两次。

返回一个大小为 2 的数组 result，其中 result[0] 是最长特殊路径的长度，result[1] 是所有可能的最长特殊路径中的最小节点数。

示例 1：

输入：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]
解释：最长特殊路径是 1 -> 2 -> 4 和 1 -> 3 -> 6 -> 8，长度都是 9。所有最长特殊路径中的最小节点数是 3。

示例 2：

输入：edges = [[1,0,3],[0,2,4],[0,3,5]], nums = [1,1,0,2]
输出：[5,2]
解释：最长路径是 0 -> 3，包含 2 个节点，长度为 5。

约束条件：

2 <= n <= 5 * 10^4
edges.length == n - 1
edges[i].length == 3
0 <= ui, vi < n
1 <= lengthi <= 10^3
nums.length == n
0 <= nums[i] <= 5 * 10^4
输入保证 edges 表示一个有效的树

解题思路

这道题需要在树中找到最长的特殊路径。特殊路径是从根到叶子的路径，其中所有值都不同，除了最多一个值可以出现两次。

核心思路：

DFS遍历树：从根节点0开始进行深度优先搜索，维护当前路径信息。
动态维护路径状态：
- 使用哈希表记录当前路径上每个值的最后出现位置
- 使用前缀和数组计算路径长度
- 当遇到重复值时，动态调整路径起点
路径起点调整：当在位置i遇到重复值时，需要将路径起点调整到该值上次出现位置的下一个位置，确保路径上最多只有一个值出现两次。
结果更新：在每个节点处计算当前有效路径长度，更新全局最优解。路径长度使用前缀和快速计算，节点数通过路径起点和当前位置计算。

算法步骤：

构建邻接表表示树结构
DFS过程中维护：当前路径、值的位置映射、前缀和数组、路径起点
遇到重复值时更新起点位置
在每个节点更新最长路径和最小节点数
回溯时清理状态

时间复杂度主要由DFS遍历决定，空间复杂度由路径维护的数据结构决定。

代码实现

class Solution {
public:
    vector<int> longestSpecialPath(vector<vector<int>>& edges, vector<int>& nums) {
        int n = nums.size();
        vector<vector<pair<int, int>>> graph(n);
        
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], len = edge[2];
            graph[u].push_back({v, len});
            graph[v].push_back({u, len});
        }
        
        int maxLen = 0, minNodes = 0;
        unordered_map<int, int> valuePos;
        vector<int> prefixSum;
        
        function<void(int, int, int)> dfs = [&](int node, int parent, int start) {
            prefixSum.push_back((prefixSum.empty() ? 0 : prefixSum.back()));
            
            int pos = prefixSum.size() - 1;
            int newStart = start;
            
            if (valuePos.count(nums[node])) {
                newStart = max(newStart, valuePos[nums[node]] + 1);
            }
            
            int oldPos = valuePos.count(nums[node]) ? valuePos[nums[node]] : -1;
            valuePos[nums[node]] = pos;
            
            int pathLen = prefixSum[pos] - (newStart > 0 ? prefixSum[newStart - 1] : 0);
            int nodeCount = pos - newStart + 1;
            
            if (pathLen > maxLen || (pathLen == maxLen && nodeCount < minNodes)) {
                maxLen = pathLen;
                minNodes = nodeCount;
            }
            
            for (auto [child, edgeLen] : graph[node]) {
                if (child != parent) {
                    prefixSum[pos] += edgeLen;
                    dfs(child, node, newStart);
                    prefixSum[pos] -= edgeLen;
                }
            }
            
            if (oldPos == -1) {
                valuePos.erase(nums[node]);
            } else {
                valuePos[nums[node]] = oldPos;
            }
            prefixSum.pop_back();
        };
        
        dfs(0, -1, 0);
        return {maxLen, minNodes};
    }
};

class Solution:
    def longestSpecialPath(self, edges: List[List[int]], nums: List[int]) -> List[int]:
        n = len(nums)
        graph = [[] for _ in range(n)]
        
        for u, v, length in edges:
            graph[u].append((v, length))
            graph[v].append((u, length))
        
        max_len = 0
        min_nodes = 0
        value_pos = {}
        prefix_sum = []
        
        def dfs(node, parent, start):
            nonlocal max_len, min_nodes
            
            prefix_sum.append(prefix_sum[-1] if prefix_sum else 0)
            pos = len(prefix_sum) - 1
            new_start = start
            
            if nums[node] in value_pos:
                new_start = max(new_start, value_pos[nums[node]] + 1)
            
            old_pos = value_pos.get(nums[node], -1)
            value_pos[nums[node]] = pos
            
            path_len = prefix_sum[pos] - (prefix_sum[new_start - 1] if new_start > 0 else 0)
            node_count = pos - new_start + 1
            
            if path_len > max_len or (path_len == max_len and node_count < min_nodes):
                max_len = path_len
                min_nodes = node_count
            
            for child, edge_len in graph[node]:
                if child != parent:
                    prefix_sum[pos] += edge_len
                    dfs(child, node, new_start)
                    prefix_sum[pos] -= edge_len
            
            if old_pos == -1:
                del value_pos[nums[node]]
            else:
                value_pos[nums[node]] = old_pos
            prefix_sum.pop()
        
        dfs(0, -1, 0)
        return [max_len, min_nodes]

public class Solution {
    public int[] LongestSpecialPath(int[][] edges, int[] nums) {
        int n = nums.Length;
        var graph = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], len = edge[2];
            graph[u].Add((v, len));
            graph[v].Add((u, len));
        }
        
        int maxLen = 0, minNodes = 0;
        var valuePos = new Dictionary<int, int>();
        var prefixSum = new List<int>();
        
        void Dfs(int node, int parent, int start) {
            prefixSum.Add(prefixSum.Count > 0 ? prefixSum[^1] : 0);
            int pos = prefixSum.Count - 1;
            int newStart = start;
            
            if (valuePos.ContainsKey(nums[node])) {
                newStart = Math.Max(newStart, valuePos[nums[node]] + 1);
            }
            
            int oldPos = valuePos.ContainsKey(nums[node]) ? valuePos[nums[node]] : -1;
            valuePos[nums[node]] = pos;
            
            int pathLen = prefixSum[pos] - (newStart > 0 ? prefixSum[newStart - 1] : 0);
            int nodeCount = pos - newStart + 1;
            
            if (pathLen > maxLen || (pathLen == maxLen && nodeCount < minNodes)) {
                maxLen = pathLen;
                minNodes = nodeCount;
            }
            
            foreach (var (child, edgeLen) in graph[node]) {
                if (child != parent) {
                    prefixSum[pos] += edgeLen;
                    Dfs(child, node, newStart);
                    prefixSum[pos] -= edgeLen;
                }
            }
            
            if (oldPos == -1) {
                valuePos.Remove(nums[node]);
            } else {
                valuePos[nums[node]] = oldPos;
            }
            prefixSum.RemoveAt(prefixSum.Count - 1);
        }
        
        Dfs(0, -1, 0);
        return new int[] { maxLen, minNodes };
    }
}

/**
 * @param {number[][]} edges
 * @param {number[]} nums
 * @return {number[]}
 */
var longestSpecialPath = function(edges, nums) {
    const n = nums.length;
    const graph = Array(n).fill().map(() => []);
    
    for (const [u, v, len] of edges) {
        graph[u].push([v, len]);
        graph[v].push([u, len]);
    }
    
    let maxLength = 0;
    let minNodes = Infinity;
    
    function dfs(node, parent, visited, duplicateUsed, currentLength, nodeCount) {
        const value = nums[node];
        
        if (visited.has(value)) {
            if (duplicateUsed) return;
            duplicateUsed = true;
        }
        
        visited.add(value);
        
        if (currentLength > maxLength) {
            maxLength = currentLength;
            minNodes = nodeCount;
        } else if (currentLength === maxLength) {
            minNodes = Math.min(minNodes, nodeCount);
        }
        
        for (const [child, edgeLen] of graph[node]) {
            if (child === parent) continue;
            
            const childValue = nums[child];
            const wouldCreateInvalidDuplicate = visited.has(childValue) && duplicateUsed;
            
            if (!wouldCreateInvalidDuplicate) {
                dfs(child, node, new Set(visited), duplicateUsed, currentLength + edgeLen, nodeCount + 1);
            }
        }
    }
    
    for (let i = 0; i < n; i++) {
        dfs(i, -1, new Set(), false, 0, 1);
    }
    
    return [maxLength, minNodes];
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n)	每个节点访问一次，每次访问的操作均为常数时间
空间复杂度	O(n)	递归栈深度最多为O(n)，辅助数据结构空间也为O(n)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目