力扣2846 边权重均等查询 从LCA到路径处理的深度解析

一、问题重述

给定一棵n个节点的树，每个边有一个权重值。需要处理多个查询，每个查询给出两个节点u和v，要求将u到v路径上所有边的权重变成相同值的最小操作次数（每次操作可将某边权重+1或-1）。

二、解题思路

核心算法采用LCA（最低公共祖先）+路径统计：

1. 预处理每个节点的深度和父节点信息

2. 使用二进制提升法快速查询LCA

3. 统计路径上各权重的出现频次

4. 计算将所有边变为众数的最小操作次数

三、完整C++代码

#include <vector>
#include <algorithm>
using namespACe std;

class Solution {
    vector<vector<pair<int, int>>> adj; // 邻接表：{节点, 边权}
    vector<vector<int>> parent;         // 二进制提升父节点表
    vector<int> depth;                  // 节点深度
    vector<array<int, 27>> cnt;         // 节点到根的各权重计数
    
public:
    vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
        // 初始化
        adj.resize(n);
        parent.assign(n, vector<int>(20, -1));
        depth.resize(n);
        cnt.resize(n);
        for(auto& e : edges) {
            adj[e[0]].emplace_back(e[1], e[2]);
            adj[e[1]].emplace_back(e[0], e[2]);
        }
        
        // DFS预处理
        dfs(0, -1, 0);
        
        // 二进制提升预处理
        for(int k = 1; k < 20; ++k) {
            for(int u = 0; u < n; ++u) {
                if(parent[u][k-1] != -1) {
                    parent[u][k] = parent[parent[u][k-1]][k-1];
                }
            }
        }
        
        // 处理查询
        vector<int> res;
        for(auto& q : queries) {
            int u = q[0], v = q[1];
            int l = lca(u, v);
            
            // 合并路径上的权重计数
            array<int, 27> total{};
            for(int i = 1; i <= 26; ++i) {
                total[i] = cnt[u][i] + cnt[v][i] - 2 * cnt[l][i];
            }
            
            // 计算操作次数
            int sum = 0, max_cnt = 0;
            for(int i = 1; i <= 26; ++i) {
                sum += total[i];
                max_cnt = max(max_cnt, total[i]);
            }
            res.push_back(sum - max_cnt);
        }
        return res;
    }
    
private:
    void dfs(int u, int p, int d) {
        parent[u][0] = p;
        depth[u] = d;
        if(p != -1) {
            // 继承父节点的计数
            cnt[u] = cnt[p];
            // 更新当前边的权重计数
            for(auto& [v, w] : adj[u]) {
                if(v == p) {
                    cnt[u][w]++;
                    break;
                }
            }
        }
        // 递归处理子节点
        for(auto& [v, w] : adj[u]) {
            if(v != p) dfs(v, u, d+1);
        }
    }
    
    int lca(int u, int v) {
        // 确保u是较深的节点
        if(depth[u] < depth[v]) swap(u, v);
        // 提升u到与v同深度
        for(int k = 19; k >= 0; --k) {
            if(depth[u] - (1 << k) >= depth[v]) {
                u = parent[u][k];
            }
        }
        if(u == v) return u;
        // 同时提升u和v
        for(int k = 19; k >= 0; --k) {
            if(parent[u][k] != -1 && parent[u][k] != parent[v][k]) {
                u = parent[u][k];
                v = parent[v][k];
            }
        }
        return parent[u][0];
    }
};

四、关键算法详解

1. 数据结构设计

• 邻接表adj：存储树的边关系，每个元素是pair<邻接节点, 边权>

• parent数组：二进制提升表，parent[u][k]表示节点u向上2^k步的祖先

• cnt数组：记录从根到每个节点路径上各权重出现的次数

2. DFS预处理

通过深度优先搜索完成三件事：

1. 记录每个节点的直接父节点

2. 计算节点深度

3. 统计根到当前节点路径上的权重分布

3. 二进制提升法

预处理每个节点向上2^k步的祖先，将LCA查询复杂度从O(n)优化到O(logn)。核心思想是利用二进制拆分，将线性查找转化为对数级别的跳跃查询。

4. 查询处理流程

对于每个查询u-v：

1. 找到它们的LCA节点l

2. 计算路径u-l-v上的权重分布

3. 找出出现次数最多的权重（众数）

4. 计算将所有边变为众数的最小操作次数

五、复杂度分析

• 预处理：O(nlog n)时间，O(nlog n)空间

• 查询：O(log n + 26)时间（26是权重的可能取值范围）

• 总复杂度：O(nlog n + q(log n + 26))，其中q是查询次数