LCA + 倍增数组优化
无向图中某两点之间的路径是唯一确定的,要求最小的操作数使得树中某两个点之间的路径上所有边的长度相同,那么该路径上要保留的边权就出现次数最多的边权。求最小操作数,我们需要统计两点之间路径上的边数,以及不同边权的出现次数。
对于图中a
, b
两点之间的路径,可以由该路径上的最高点(深度最小的点)确定,而这个最高点就是该两点的LCA
,该路径的边数total
就等于:
total = (a的深度 - lca的深度) + (b的深度 - lca的深度)
通过DFS预处理各点的深度数组depth
,以及根节点到各点i
路径上的不同边权的出现次数cnt[i]
。
寻找LCA的方法可以通过倍增数组找到,倍增数组parent[i][j
]表示节点i
的第2^j
个祖先节点;在寻找点a
和点b
的LCA之前,需要先调节深度更深的点,使得两点深度相同,将a
,b
两点的深度统一。若统一深度后有a == b
,则说明a
就是a
、b
两点的LCA,否则a
和b
两点出发同时往上走2^i
步,根据a
和b
的第2^i
个祖先节点是否相同,有:
若
a
和b
的第2^i
个祖先不相同,说明a
和b
的LCA是在更上层的节点,此时将a
,b
转移到其第2^i
个祖先的位置上,i--
;
若a
和b
的第2^i
个祖先相同,说明这个祖先可能是LCA,也可能是比LCA更上层的一个节点,此时保持a
,b
不动,i--
;
从大到小遍历i
,直到i == 0
,此时a
和b
就是其LCA的两个子节点。
找到a
和b
的LCA后,对于a
到b
的路径上个边权w
的出现次数,就有:
根节点到a的路径中w的出现次数 + 根节点到b的路径中w的出现次数 - 2 * 根节点到LCA的路径中w的出现次数
根据a
, b
和LCA的深度数组以及边权统计数,a
、b
两点间的最少操作数res为:res = total - 各边权中的最大出现数
。
寻找LCA的时间复杂度为O(logn)
https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/solutions/2424060/lca-mo-ban-by-endlesscheng-j54b/
C++ 代码
class Solution {
public:
vector<int> minOperationsQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries) {
vector<vector<vector<int>>> g(n);
for(auto& edge : edges) {
int a = edge[0], b = edge[1], w = edge[2] - 1;
g[a].push_back({b, w});
g[b].push_back({a, w});
}
int m = 32 - __builtin_clz(n); // m为n的二进制长度
vector<vector<int>> parent(n, vector<int>(m, -1)); // parent[i][j]表示第i个节点的第2^j个祖先节点
vector<vector<int>> cnt(n, vector<int>(26, 0)); // 统计0 -> i路径上各边权出现次数
vector<int> depth(n);
// DFS求个节点的深度以及统计根节点到各点的边权出现次数
function<void(int, int)> DFS = [&](int x, int father) -> void {
parent[x][0] = father;
// x -> y
for(auto& edge : g[x]) {
int y = edge[0], w = edge[1];
if(y == father) continue;
depth[y] = depth[x] + 1;
for(int i = 0; i < 26; i++) cnt[y][i] = cnt[x][i];
cnt[y][w]++;
DFS(y, x);
}
};
DFS(0, -1);
// 预处理祖先数组
for(int j = 1; j < m; j++) {
for(int i = 0; i < n; i++) {
if(parent[i][j - 1] != -1)
parent[i][j] = parent[parent[i][j - 1]][j - 1];
}
}
function<int(int, int)> findLCA = [&](int a, int b) -> int {
// 统一为a为更高的节点,b为更低的节点
if(depth[a] > depth[b]) swap(a, b);
// 先让a,b两点深度相同,让b往上跳
for(int i = m - 1; i >= 0; i--) {
if(parent[b][i] != -1 && depth[parent[b][i]] >= depth[a])
b = parent[b][i];
}
// 若b == a,a是a和b的LCA
if(a == b) return a;
// a本身不是a和b的LAC,开始寻找LCA
for(int i = m - 1; i >= 0; i--) {
// 该祖先为LCA或者比LAC更上层的节点,a和b不动
if(parent[a][i] == -1 || parent[a][i] == parent[b][i]) continue;
// 还没找到LCA,a和b一起往上走
a = parent[a][i], b = parent[b][i];
}
// 此时LAC就是a和b的父节点
return parent[a][0];
};
vector<int> res;
for(auto& q : queries) {
int a = q[0], b = q[1];
int total = depth[a] + depth[b];
int lca = findLCA(a, b);
total -= 2 * depth[lca]; // 计算出a->b的路径边数
// 统计a->b路径上个边权出现次数
int max_cnt = 0;
for(int i = 0; i < 26; i++) {
max_cnt = max(max_cnt, cnt[q[0]][i] + cnt[q[1]][i] - 2 * cnt[lca][i]);
}
res.push_back(total - max_cnt);
}
return res;
}
};