省流:注意 if (u == v) return res;
以下是我的代码:
int getmin(int u, int v) {
if (not intree[u] or not intree[v]) return -1;
if (deep[u] > deep[v]) swap(u, v);
int res = inf;
for (int i = lgmxn - 1; i >= 0; --i)
if (deep[fa[v][i]] >= deep[u]) {
res = min(res, minw[v][i]);
v = fa[v][i];
}
for (int i = lgmxn - 1; i >= 0; --i)
if (fa[u][i] != fa[v][i]) {
res = min({res, minw[u][i], minw[v][i]});
u = fa[u][i], v = fa[v][i];
}
res = min({res, minw[u][0], minw[v][0]});
return res;
}
开始死活找不到错误,跟#1题解对比发现少了 if (u == v) return res;
考虑两个节点为祖先-后代关系。当第一次将两个节点抬升到同深度后虽然不会进行“同时倍增跳”的环节但是 res = min({res, minw[u][0], minw[v][0]}); 依然被执行。连接这个节点与父亲的边权被错误计算。