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

rhsgfswg

一、问题重述

给定一棵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是查询次数
  
  

来源：竞赛资料