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也可能通过父亲结点连一条虚边呀