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

胡志明t

一、问题重述

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

二、解题思路

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

• 预处理每个节点的深度和父节点信息
• 使用二进制提升法快速查询LCA
• 统计路径上各权重的出现频次
• 计算将所有边变为众数的最小操作次数
  
  

三、完整C++代码

1. #include <vector>
   
2. #include <algorithm>
   
3. using namespACe std;
   
4. 
   
5. class Solution {
   
6.     vector<vector<pair<int, int>>> adj; // 邻接表：{节点, 边权}
   
7.     vector<vector<int>> parent;         // 二进制提升父节点表
   
8.     vector<int> depth;                  // 节点深度
   
9.     vector<array<int, 27>> cnt;         // 节点到根的各权重计数
   
10.    
    
11. public:
    
12.     vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
    
13.         // 初始化
    
14.         adj.resize(n);
    
15.         parent.assign(n, vector<int>(20, -1));
    
16.         depth.resize(n);
    
17.         cnt.resize(n);
    
18.         for(auto& e : edges) {
    
19.             adj[e[0]].emplace_back(e[1], e[2]);
    
20.             adj[e[1]].emplace_back(e[0], e[2]);
    
21.         }
    
22.         
    
23.         // DFS预处理
    
24.         dfs(0, -1, 0);
    
25.         
    
26.         // 二进制提升预处理
    
27.         for(int k = 1; k < 20; ++k) {
    
28.             for(int u = 0; u < n; ++u) {
    
29.                 if(parent[u][k-1] != -1) {
    
30.                     parent[u][k] = parent[parent[u][k-1]][k-1];
    
31.                 }
    
32.             }
    
33.         }
    
34.         
    
35.         // 处理查询
    
36.         vector<int> res;
    
37.         for(auto& q : queries) {
    
38.             int u = q[0], v = q[1];
    
39.             int l = lca(u, v);
    
40.             
    
41.             // 合并路径上的权重计数
    
42.             array<int, 27> total{};
    
43.             for(int i = 1; i <= 26; ++i) {
    
44.                 total[i] = cnt[u][i] + cnt[v][i] - 2 * cnt[l][i];
    
45.             }
    
46.             
    
47.             // 计算操作次数
    
48.             int sum = 0, max_cnt = 0;
    
49.             for(int i = 1; i <= 26; ++i) {
    
50.                 sum += total[i];
    
51.                 max_cnt = max(max_cnt, total[i]);
    
52.             }
    
53.             res.push_back(sum - max_cnt);
    
54.         }
    
55.         return res;
    
56.     }
    
57.    
    
58. private:
    
59.     void dfs(int u, int p, int d) {
    
60.         parent[u][0] = p;
    
61.         depth[u] = d;
    
62.         if(p != -1) {
    
63.             // 继承父节点的计数
    
64.             cnt[u] = cnt[p];
    
65.             // 更新当前边的权重计数
    
66.             for(auto& [v, w] : adj[u]) {
    
67.                 if(v == p) {
    
68.                     cnt[u][w]++;
    
69.                     break;
    
70.                 }
    
71.             }
    
72.         }
    
73.         // 递归处理子节点
    
74.         for(auto& [v, w] : adj[u]) {
    
75.             if(v != p) dfs(v, u, d+1);
    
76.         }
    
77.     }
    
78.    
    
79.     int lca(int u, int v) {
    
80.         // 确保u是较深的节点
    
81.         if(depth[u] < depth[v]) swap(u, v);
    
82.         // 提升u到与v同深度
    
83.         for(int k = 19; k >= 0; --k) {
    
84.             if(depth[u] - (1 << k) >= depth[v]) {
    
85.                 u = parent[u][k];
    
86.             }
    
87.         }
    
88.         if(u == v) return u;
    
89.         // 同时提升u和v
    
90.         for(int k = 19; k >= 0; --k) {
    
91.             if(parent[u][k] != -1 && parent[u][k] != parent[v][k]) {
    
92.                 u = parent[u][k];
    
93.                 v = parent[v][k];
    
94.             }
    
95.         }
    
96.         return parent[u][0];
    
97.     }
    
98. };

复制代码

四、关键算法详解1. 数据结构设计

• 邻接表adj：存储树的边关系，每个元素是pair<邻接节点, 边权>
• parent数组：二进制提升表，parent[k]表示节点u向上2^k步的祖先
• cnt数组：记录从根到每个节点路径上各权重出现的次数
  
  

2. DFS预处理

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

• 记录每个节点的直接父节点
• 计算节点深度
• 统计根到当前节点路径上的权重分布
  
  

3. 二进制提升法

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

4. 查询处理流程

对于每个查询u-v：

• 找到它们的LCA节点l
• 计算路径u-l-v上的权重分布
• 找出出现次数最多的权重（众数）
• 计算将所有边变为众数的最小操作次数
  
  

五、复杂度分析

• 预处理：O(nlog n)时间，O(nlog n)空间
• 查询：O(log n + 26)时间（26是权重的可能取值范围）
• 总复杂度：O(nlog n + q(log n + 26))，其中q是查询次数
  
  

来源：竞赛资料