3425. 最长特殊路径

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,2],[1,2,3],[1,3,5],[1,4,4],[2,5,6]], nums = [2,1,2,1,3,1]
输出：[6,2]
解释：最长的特殊路径是 2 -> 5 和 0 -> 1 -> 4，长度都是 6。所有最长特殊路径中的最少节点数是 2。

示例 2：

输入：edges = [[1,0,8]], nums = [2,2]
输出：[0,1]
解释：最长的特殊路径是 0 和 1，长度都是 0。所有最长特殊路径中的最少节点数是 1。

约束条件：

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）来解决。

核心思路：

对于每个节点，我们需要计算从根到该节点的所有特殊路径
使用哈希表记录从根到当前路径中每个值最后出现的位置
利用前缀和思想，当遇到重复值时，特殊路径只能从该值上次出现位置之后开始
维护全局最长路径长度和对应的最少节点数

算法步骤：

构建邻接表表示树结构
DFS遍历时维护从根到当前节点的路径信息：
- 累计距离（前缀和）
- 每个值最后出现的位置
对于当前节点，计算以该节点结尾的最长特殊路径：
- 如果当前值之前出现过，路径从上次出现位置之后开始
- 否则路径从根开始
更新全局最优解，记录最长距离和对应的最少节点数

时间复杂度优化： 使用前缀和避免重复计算路径长度，使得每次计算特殊路径长度为O(1)。

代码实现

class Solution {
public:
    vector<int> longestSpecialPath(vector<vector<int>>& edges, vector<int>& nums) {
        int n = nums.size();
        vector<vector<pair<int, int>>> adj(n);
        
        // 构建邻接表
        for (auto& edge : edges) {
            adj[edge[0]].push_back({edge[1], edge[2]});
            adj[edge[1]].push_back({edge[0], edge[2]});
        }
        
        int maxLen = 0, minNodes = 1;
        
        function<void(int, int, vector<long long>&, unordered_map<int, int>&)> dfs = 
            [&](int node, int parent, vector<long long>& prefixSum, unordered_map<int, int>& lastPos) {
            
            int startIdx = 0;
            if (lastPos.count(nums[node])) {
                startIdx = lastPos[nums[node]] + 1;
            }
            
            // 计算以当前节点结尾的最长特殊路径
            long long pathLen = prefixSum.back() - (startIdx > 0 ? prefixSum[startIdx - 1] : 0);
            int pathNodes = prefixSum.size() - startIdx;
            
            if (pathLen > maxLen || (pathLen == maxLen && pathNodes < minNodes)) {
                maxLen = pathLen;
                minNodes = pathNodes;
            }
            
            int oldPos = lastPos.count(nums[node]) ? lastPos[nums[node]] : -1;
            lastPos[nums[node]] = prefixSum.size() - 1;
            
            // 递归访问子节点
            for (auto [child, weight] : adj[node]) {
                if (child != parent) {
                    prefixSum.push_back(prefixSum.back() + weight);
                    dfs(child, node, prefixSum, lastPos);
                    prefixSum.pop_back();
                }
            }
            
            // 回溯
            if (oldPos != -1) {
                lastPos[nums[node]] = oldPos;
            } else {
                lastPos.erase(nums[node]);
            }
        };
        
        vector<long long> prefixSum = {0};
        unordered_map<int, int> lastPos;
        dfs(0, -1, prefixSum, lastPos);
        
        return {maxLen, minNodes};
    }
};

class Solution:
    def longestSpecialPath(self, edges: List[List[int]], nums: List[int]) -> List[int]:
        n = len(nums)
        adj = [[] for _ in range(n)]
        
        # 构建邻接表
        for u, v, w in edges:
            adj[u].append((v, w))
            adj[v].append((u, w))
        
        max_len = 0
        min_nodes = 1
        
        def dfs(node, parent, prefix_sum, last_pos):
            nonlocal max_len, min_nodes
            
            start_idx = 0
            if nums[node] in last_pos:
                start_idx = last_pos[nums[node]] + 1
            
            # 计算以当前节点结尾的最长特殊路径
            path_len = prefix_sum[-1] - (prefix_sum[start_idx - 1] if start_idx > 0 else 0)
            path_nodes = len(prefix_sum) - start_idx
            
            if path_len > max_len or (path_len == max_len and path_nodes < min_nodes):
                max_len = path_len
                min_nodes = path_nodes
            
            old_pos = last_pos.get(nums[node], -1)
            last_pos[nums[node]] = len(prefix_sum) - 1
            
            # 递归访问子节点
            for child, weight in adj[node]:
                if child != parent:
                    prefix_sum.append(prefix_sum[-1] + weight)
                    dfs(child, node, prefix_sum, last_pos)
                    prefix_sum.pop()
            
            # 回溯
            if old_pos != -1:
                last_pos[nums[node]] = old_pos
            else:
                del last_pos[nums[node]]
        
        dfs(0, -1, [0], {})
        return [max_len, min_nodes]

public class Solution {
    public int[] LongestSpecialPath(int[][] edges, int[] nums) {
        int n = nums.Length;
        var adj = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<(int, int)>();
        }
        
        // 构建邻接表
        foreach (var edge in edges) {
            adj[edge[0]].Add((edge[1], edge[2]));
            adj[edge[1]].Add((edge[0], edge[2]));
        }
        
        int maxLen = 0, minNodes = 1;
        
        void Dfs(int node, int parent, List<long> prefixSum, Dictionary<int, int> lastPos) {
            int startIdx = 0;
            if (lastPos.ContainsKey(nums[node])) {
                startIdx = lastPos[nums[node]] + 1;
            }
            
            // 计算以当前节点结尾的最长特殊路径
            long pathLen = prefixSum[^1] - (startIdx > 0 ? prefixSum[startIdx - 1] : 0);
            int pathNodes = prefixSum.Count - startIdx;
            
            if (pathLen > maxLen || (pathLen == maxLen && pathNodes < minNodes)) {
                maxLen = (int)pathLen;
                minNodes = pathNodes;
            }
            
            int oldPos = lastPos.GetValueOrDefault(nums[node], -1);
            lastPos[nums[node]] = prefixSum.Count - 1;
            
            // 递归访问子节点
            foreach (var (child, weight) in adj[node]) {
                if (child != parent) {
                    prefixSum.Add(prefixSum[^1] + weight);
                    Dfs(child, node, prefixSum, lastPos);
                    prefixSum.RemoveAt(prefixSum.Count - 1);
                }
            }
            
            // 回溯
            if (oldPos != -1) {
                lastPos[nums[node]] = oldPos;
            } else {
                lastPos.Remove(nums[node]);
            }
        }
        
        Dfs(0, -1, new List<long> { 0 }, new Dictionary<int, int>());
        return new int[] { maxLen, minNodes };
    }
}

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 = 1;
    
    function dfs(node, parent, visited, pathLength, nodeCount) {
        if (pathLength > maxLength || (pathLength === maxLength && nodeCount < minNodes)) {
            maxLength = pathLength;
            minNodes = nodeCount;
        }
        
        for (const [neighbor, edgeLen] of graph[node]) {
            if (neighbor !== parent && !visited.has(nums[neighbor])) {
                visited.add(nums[neighbor]);
                dfs(neighbor, node, visited, pathLength + edgeLen, nodeCount + 1);
                visited.delete(nums[neighbor]);
            }
        }
    }
    
    for (let i = 0; i < n; i++) {
        const visited = new Set([nums[i]]);
        dfs(i, -1, visited, 0, 1);
    }
    
    return [maxLength, minNodes];
};

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

复杂度分析

复杂度类型	复杂度	说明
时间复杂度	O(n)	每个节点访问一次，每次操作为O(1)
空间复杂度	O(n)	递归栈深度 + 哈希表空间 + 前缀和数组

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目