如果您使用和我一样的倍增 LCA 写法
void dfs(int f, int u, int d) {
fa[u][0]=f; dep[u]=d;
for(auto& x:edge[u]) if(x!=f) dfs(u, x, d+1);
}
void init() {
f(T,1,19) f(i,1,n) fa[i][T]=fa[fa[i][T-1]][T-1];
}
int lca(int x, int y) {
if(x==y) return x;
if(dep[x]<dep[y]) swap(x, y);
d(i,0,19) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
//printf("x=%d, y=%d\n", x, y);
if(x==y) return x;
d(i,0,19) if(fa[x][i]!=fa[y][i]) x=fa[x][i], y=fa[y][i];
return fa[x][0];
}
请注意不要使用 dfs(0, 1, 0)
, 即把 dep[1] 设为 0. 这会导致在查询某节点和 1 的 LCA 时得到错误的答案 0. 调了一周的线段树合并发现是这个错了 = =