Prutekoi's blog

LCT真的短..

LCT查子树

我们知道一般的LCT只能对链进行操作,支持加边删边,链加链求和之类的。
那么如果需要动态加边然后查子树和呢?
首先,普通的LCT不能查询子树是因为它只维护了实链(即每棵splay)的信息,而轻链没有维护。那么我们在普通的splay基础上多维护一个轻链就好了。
如果我们有这么一个数组$si[x]$表示$x$的所有虚儿子的子树和的和,那么我们只需要简单修改一下update函数就好了。
而我们发现影响虚儿子的操作只有access和link,其中access是更换了实儿子,link是新增了虚儿子。注意维护一下就好了。实际代码只多了3句话...

void update(int x){s[x]=s[lc]+s[rc]+si[x]+val[x];}
void access(int x){
    int y=x,tp=0;st[++tp]=y;
    while(y)st[++tp]=y=f[y];
    while(tp)pushdown(st[tp--]);
    for(;x;x=f[y=x])splay(x),si[x]+=s[rc]-s[y],rc=y;
}
void link(int x,int y){
    split(x,y);f[x]=y;si[y]+=s[x];
}

还有一个要特别注意的地方。子树和其实是所有的虚儿子的和加上自己再加上右儿子的子树和。于是要查询子树和时要让这个点没有左儿子。可以通过$makeroot$等操作实现。具体来说,要查$x$为根时$y$的子树和,先$makeroot(x)$,然后找出$y$在原树上的父亲,即$y$的左儿子,没有左儿子就是父亲(考虑中序遍历),设为$z$。然后$makeroot(y),access(z),splay(z)$,则$s[y]$即为所求。(发现z没有这么好求qwq)
其实这玩意可以先把要查的这个点先splay到根，然后它的左子树就是祖先，右子树就是子孙。那么查这个点的右子树的信息，再加上本身的信息就行了...

LCT虽然可以查子树但是无法优美地修改子树。那就是toptree的事了..咕咕咕(这个真有可能咕到退役)