提问有关动态树(LCT)的link操作
  • 板块学术版
  • 楼主propane
  • 当前回复7
  • 已保存回复7
  • 发布时间2022/1/24 00:47
  • 上次更新2023/10/28 11:22:32
查看原帖
提问有关动态树(LCT)的link操作
546401
propane楼主2022/1/24 00:47
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的根节点,然后在xy之间连一条虚边。 那么为什么LCT的操作能保证连虚边之前x的父亲节点一定为0呢?不能理解。因为感觉翻转x所在的子树虽然可以保证x是原树的根,但是x也可能通过父亲结点连一条虚边呀

2022/1/24 00:47
加载中...