关于 makeroot
查看原帖
关于 makeroot
358748
Error_Yuan楼主2022/7/7 09:51

rt,OIwiki 上的 access 和 makeroot 长这样:

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;
}
inline void makeRoot(int p) {
  p = Access(p);
  swap(ch[p][0], ch[p][1]);
  rev[p] ^= 1;
}

发现假掉了,但是如果把 makeroot 改成下面这样就对了:

void makeRoot(int x) {
	access(x);
	splay(x);
	rev[x] ^= 1;
	swap(ch[x][0], ch[x][1]);
}

为什么?

2022/7/7 09:51
加载中...