void makeroot(int x){
access(x);
pushrev(x);
}
int findroot(int x){
access(x);
while(tr[x].s[0]) x = tr[x].s[0];
splay(x);
return x;
}
void link(int x, int y){
makeroot(x);
if (findroot(y) != x) tr[x].p = y;
}
动态树的link
操作,先把x
变为原树的根,findroot(y)
过程中会把y
所在树的根节点(其实也就是x
)转到Splay
的根节点,然后在x
跟y
之间连一条虚边。
那么为什么LCT
的操作能保证连虚边之前x的父亲节点一定为0呢?不能理解。因为感觉翻转x
所在的子树虽然可以保证x
是原树的根,但是x
也可能通过父亲结点连一条虚边呀