社区讨论

关于 makeroot

EError_Yuan
P3690【模板】动态树（LCT）参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo8nttnw
此快照首次捕获于
2023/10/27 21:39
2 年前
此快照最后确认于
2023/10/27 21:39
2 年前
查看原帖
rt，OIwiki 上的 access 和 makeroot 长这样：
CPP
inline int Access(int x) {
  int p;
  for (p = 0; x; p = x, x = fa[x]) {
    Splay(x), ch[x][1] = p, PushUp(x);
  }
  return p;
}
CPP
inline void makeRoot(int p) {
  p = Access(p);
  swap(ch[p][0], ch[p][1]);
  rev[p] ^= 1;
}
发现假掉了，但是如果把 makeroot 改成下面这样就对了：
CPP
void makeRoot(int x) {
	access(x);
	splay(x);
	rev[x] ^= 1;
	swap(ch[x][0], ch[x][1]);
}
为什么？

回复

共 1 条回复，欢迎继续交流。

正在加载回复...