在网上看到一个版本 link cut 两种操作均未使用 find_root 的操作。有两个问题:
- 这样的 合理性 ?
- 如果合理,为什么 合理?
求助!!
这里是提交记录 record,请留意注释部分。
void link(int x, int y) {
mkroot(x);
if (root(y) != x) {
f[x] = y;
}
}
void cut(int x, int y) {
mkroot(x);
if (root(y) == x && f[y] == x && !son[x][0]) {
son[x][1] = f[y] = 0, up(x);
}
}