为什么不能用Lca判断2点 是否在同一块呢?
∵dfs(1) 的时候,不会 dfs 到另一块,所以 Lca 的 fa[x][0] 的判断不会执行到,无法 return−1。
inline int Lca(int x, int y) {
if(dep[x] > dep[y]) swap(x, y);
if(dep[x] == dep[y]) goto L;
int tx, ty;
for(int j=20;j>=0;--j) {
ty = fat[y][j];
if(ty == 0) continue;
if(dep[ty] >= dep[x]) y = ty;
if(dep[y] == dep[x]) break;
}
L:
if(x == y) return d[x];
for(int j=20;j>=0;--j) {
tx = fat[x][j];
ty = fat[y][j];
if(tx==0 || ty==0) continue;
if(tx == ty) continue;
x = tx;
y = ty;
}
return d[fat[x][0]];
}