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]);
}
为什么?