Hard

题目描述

给定一个有 n 个节点的无向树，节点标号从 0 到 n - 1。给定整数 n 和长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ui, vi, wi] 表示节点 ui 和 vi 之间有一条权重为 wi 的边。

还给定一个长度为 m 的二维整数数组 queries，其中 queries[i] = [ai, bi]。对于每个查询，找到使从 ai 到 bi 路径上每条边的权重都相等所需的最小操作数。在一次操作中，你可以选择树的任意一条边并将其权重改为任意值。

注意：

  • 查询彼此独立，意味着每个新查询时树都会回到初始状态
  • 从 ai 到 bi 的路径是一个不同节点的序列，以节点 ai 开始，以节点 bi 结束，序列中每两个相邻节点在树中共享一条边

返回长度为 m 的数组 answer，其中 answer[i] 是第 i 个查询的答案。

示例 1:

输入: n = 7, edges = [[0,1,1],[1,2,1],[2,3,1],[3,4,2],[4,5,2],[5,6,2]], queries = [[0,3],[3,6],[2,6],[0,6]]
输出: [0,0,1,3]

示例 2:

输入: n = 8, edges = [[1,2,6],[1,3,4],[2,4,6],[2,5,3],[3,6,6],[3,0,8],[7,0,2]], queries = [[4,6],[0,4],[6,5],[7,4]]
输出: [1,2,2,3]

约束:

  • 1 <= n <= 10^4
  • edges.length == n - 1
  • edges[i].length == 3
  • 0 <= ui, vi < n
  • 1 <= wi <= 26
  • 输入保证 edges 表示有效的树
  • 1 <= queries.length == m <= 2 * 10^4
  • queries[i].length == 2
  • 0 <= ai, bi < n

解题思路

这道题目的核心思路是：对于路径上的所有边，我们需要统计每种权重出现的次数，然后选择出现次数最多的权重作为目标权重，其他边都需要修改，操作次数就是总边数减去最多权重的边数。

解题步骤：

  1. 构建图和预处理：使用邻接表构建无向树，并进行 DFS 预处理，记录每个节点到根节点路径上各种权重的出现次数。

  2. LCA 算法：使用二分提升（Binary Lifting）算法快速计算最近公共祖先，这样可以高效地处理查询。

  3. 路径权重统计：对于查询 [a, b]，路径上权重 w 的出现次数等于 freq[a][w] + freq[b][w] - 2 * freq[lca(a,b)][w]。这是因为 LCA 到根的路径被重复计算了两次。

  4. 计算最小操作数：统计路径上所有权重的频次，找出最大频次，总边数减去最大频次即为答案。

由于边权重范围是 1-26，可以用数组直接记录每种权重的频次，时间复杂度很低。

推荐解法：使用二分提升 + 路径频次统计的方法，能够高效处理大量查询。

代码实现

class Solution {
public:
    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        // 构建邻接表
        vector<vector<pair<int, int>>> graph(n);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        
        // 二分提升预处理
        int logN = 15; // log2(10^4) < 15
        vector<vector<int>> parent(n, vector<int>(logN, -1));
        vector<int> depth(n);
        vector<vector<int>> freq(n, vector<int>(27, 0)); // 权重范围1-26
        
        // DFS 预处理
        function<void(int, int, int)> dfs = [&](int u, int p, int d) {
            parent[u][0] = p;
            depth[u] = d;
            
            // 二分提升预处理
            for (int i = 1; i < logN && parent[u][i-1] != -1; i++) {
                parent[u][i] = parent[parent[u][i-1]][i-1];
            }
            
            for (auto& [v, w] : graph[u]) {
                if (v != p) {
                    // 继承父节点的频次并加上当前边的权重
                    freq[v] = freq[u];
                    freq[v][w]++;
                    dfs(v, u, d + 1);
                }
            }
        };
        
        dfs(0, -1, 0);
        
        // LCA函数
        auto lca = [&](int u, int v) {
            if (depth[u] < depth[v]) swap(u, v);
            
            // 将u提升到与v相同深度
            int diff = depth[u] - depth[v];
            for (int i = 0; i < logN; i++) {
                if ((diff >> i) & 1) {
                    u = parent[u][i];
                }
            }
            
            if (u == v) return u;
            
            // 同时向上提升直到找到LCA
            for (int i = logN - 1; i >= 0; i--) {
                if (parent[u][i] != parent[v][i]) {
                    u = parent[u][i];
                    v = parent[v][i];
                }
            }
            
            return parent[u][0];
        };
        
        vector<int> result;
        for (auto& query : queries) {
            int a = query[0], b = query[1];
            int lca_node = lca(a, b);
            
            // 计算路径上每种权重的频次
            vector<int> pathFreq(27, 0);
            int totalEdges = 0;
            
            for (int w = 1; w <= 26; w++) {
                pathFreq[w] = freq[a][w] + freq[b][w] - 2 * freq[lca_node][w];
                totalEdges += pathFreq[w];
            }
            
            // 找最大频次
            int maxFreq = 0;
            for (int w = 1; w <= 26; w++) {
                maxFreq = max(maxFreq, pathFreq[w]);
            }
            
            result.push_back(totalEdges - maxFreq);
        }
        
        return result;
    }
};

class Solution:
    def minOperationsQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
        from collections import defaultdict
        
        # 构建邻接表
        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        # 二分提升预处理
        logN = 15
        parent = [[-1] * logN for _ in range(n)]
        depth = [0] * n
        freq = [[0] * 27 for _ in range(n)]  # 权重范围1-26
        
        def dfs(u, p, d):
            parent[u][0] = p
            depth[u] = d
            
            # 二分提升预处理
            for i in range(1, logN):
                if parent[u][i-1] != -1:
                    parent[u][i] = parent[parent[u][i-1]][i-1]
                else:
                    break
            
            for v, w in graph[u]:
                if v != p:
                    # 继承父节点的频次并加上当前边的权重
                    freq[v] = freq[u][:]
                    freq[v][w] += 1
                    dfs(v, u, d + 1)
        
        dfs(0, -1, 0)
        
        def lca(u, v):
            if depth[u] < depth[v]:
                u, v = v, u
            
            # 将u提升到与v相同深度
            diff = depth[u] - depth[v]
            for i in range(logN):
                if (diff >> i) & 1:
                    u = parent[u][i]
            
            if u == v:
                return u
            
            # 同时向上提升直到找到LCA
            for i in range(logN - 1, -1, -1):
                if parent[u][i] != parent[v][i]:
                    u = parent[u][i]
                    v = parent[v][i]
            
            return parent[u][0]
        
        result = []
        for a, b in queries:
            lca_node = lca(a, b)
            
            # 计算路径上每种权重的频次
            pathFreq = [0] * 27
            totalEdges = 0
            
            for w in range(1, 27):
                pathFreq[w] = freq[a][w] + freq[b][w] - 2 * freq[lca_node][w]
                totalEdges += pathFreq[w]
            
            # 找最大频次
            maxFreq = max(pathFreq[1:27])
            result.append(totalEdges - maxFreq)
        
        return result

public class Solution {
    public int[] MinOperationsQueries(int n, int[][] edges, int[][] queries) {
        // 构建邻接表
        List<List<(int, int)>> graph = new List<List<(int, int)>>();
        for (int i = 0; i < n; i++) {
            graph.Add(new List<(int, int)>());
        }
        
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].Add((v, w));
            graph[v].Add((u, w));
        }
        
        // 二分提升预处理
        int logN = 15;
        int[,] parent = new int[n, logN];
        int[] depth = new int[n];
        int[,] freq = new int[n, 27]; // 权重范围1-26
        
        // 初始化parent为-1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < logN; j++) {
                parent[i, j] = -1;
            }
        }
        
        // DFS预处理
        void dfs(int u, int p, int d) {
            parent[u, 0] = p;
            depth[u] = d;
            
            // 二分提升预处理
            for (int i = 1; i < logN && parent[u, i-1] != -1; i++) {
                parent[u, i] = parent[parent[u, i-1], i-1];
            }
            
            foreach (var (v, w) in graph[u]) {
                if (v != p) {
                    // 继承父节点的频次并加上当前边的权重
                    for (int i = 0; i < 27; i++) {
                        freq[v, i] = freq[u, i];
                    }
                    freq[v, w]++;
                    dfs(v, u, d + 1);
                }
            }
        }
        
        dfs(0, -1, 0);
        
        // LCA函数
        int lca(int u, int v) {
            if (depth[u] < depth[v]) {
                int temp = u; u = v; v = temp;
            }
            
            // 将u提升到与v相同深度
            int diff = depth[u] - depth[v];
            for (int i = 0; i < logN; i++) {
                if ((diff >> i & 1) == 1) {
                    u = parent[u, i];
                }
            }
            
            if (u == v) return u;
            
            // 同时向上提升直到找到LCA
            for (int i = logN - 1; i >= 0; i--) {
                if (parent[u, i] != parent[v, i]) {
                    u = parent[u, i];
                    v = parent[v, i];
                }
            }
            
            return parent[u, 0];
        }
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int a = queries[i][0], b = queries[i][1];
            int lca_node = lca(a, b);
            
            // 计算路径上每种权重的频次
            int[] pathFreq = new int[27];
            int totalEdges = 0;
            
            for (int w = 1; w <= 26; w++) {
                pathFreq[w] = freq[a, w] + freq[b, w] - 2 * freq[lca_node, w];
                totalEdges += pathFreq[w];
            }
            
            // 找最大频次
            int maxFreq = 0;
            for (int w = 1; w <= 26; w++) {
                maxFreq = Math.Max(maxFreq, pathFreq[w]);
            }
            
            result[i] = totalEdges - maxFreq;
        }
        
        return result;
    }
}

var minOperationsQueries = function(n, edges, queries) {
    const graph = Array(n).fill().map(() => []);
    
    for (const [u, v, w] of edges) {
        graph[u].push([v, w]);
        graph[v].push([u, w]);
    }
    
    const LOG = Math.ceil(Math.log2(n)) + 1;
    const parent = Array(n).fill().map(() => Array(LOG).fill(-1));
    const depth = Array(n).fill(0);
    const weightCount = Array(n).fill().map(() => Array(27).fill(0));
    
    function dfs(node, par, d) {
        parent[node][0] = par;
        depth[node] = d;
        
        for (let i = 1; i < LOG; i++) {
            if (parent[node][i - 1] !== -1) {
                parent[node][i] = parent[parent[node][i - 1]][i - 1];
            }
        }
        
        for (const [child, weight] of graph[node]) {
            if (child !== par) {
                for (let i = 1; i <= 26; i++) {
                    weightCount[child][i] = weightCount[node][i];
                }
                weightCount[child][weight]++;
                dfs(child, node, d + 1);
            }
        }
    }
    
    dfs(0, -1, 0);
    
    function lca(u, v) {
        if (depth[u] < depth[v]) [u, v] = [v, u];
        
        const diff = depth[u] - depth[v];
        for (let i = 0; i < LOG; i++) {
            if ((diff >> i) & 1) {
                u = parent[u][i];
            }
        }
        
        if (u === v) return u;
        
        for (let i = LOG - 1; i >= 0; i--) {
            if (parent[u][i] !== parent[v][i]) {
                u = parent[u][i];
                v = parent[v][i];
            }
        }
        
        return parent[u][0];
    }
    
    const result = [];
    
    for (const [a, b] of queries) {
        const lcaNode = lca(a, b);
        const pathLength = depth[a] + depth[b] - 2 * depth[lcaNode];
        
        let maxCount = 0;
        for (let w = 1; w <= 26; w++) {
            const count = weightCount[a][w] + weightCount[b][w] - 2 * weightCount[lcaNode][w];
            maxCount = Math.max(maxCount, count);
        }
        
        result.push(pathLength - maxCount);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目