题解：P11165 [BalkanOI 2023] Super Tree

· · 题解

大半年前写的题。

借鉴了一下@yangjinhua 的思路。

一个比较显然的转化是，直接维护 f，单点与可以看作子树与，路径查可以看作单点查。

考虑怎么更好地表示能量和超能量。记 s=\sum f_i，t=\sum f_i^2。显然由因式分解得能量 A=s^2，超能量就是把能量的 u=v 去掉再除以 2，超能量 B=\dfrac{s^2-t}2。所以可以先求出初始的 s 和 t 并动态维护。

不同位之间独立，下面只考虑某一位，假设当前询问 x 的这位是 0，即把一个子树这一位推平成 0。一个点一位只会被有效推平一次，即如果能做到无效推平是均摊 O(1) 的，复杂度就是对的。有两种解决方案：

一是每位维护一个并查集，能找出下一个 1 的位置（后继），一个一个跳，暴力改成 0。大半年前实现的是这个思路，但很遗憾空间被卡了。

二是虑暴力从左往右扫，如果当前位置已经是 0 了，则当前位置的子树都可以跳过。分析下时间复杂度，一个点一位只会在 1 变 0 时被遍历到一次，以及操作它的某个祖先时先遍历到它的父亲，然后展开到当前节点。接着父亲会被推平成 0，永远遍历不到。所以一个点一位无效推平只有一次。

然而现在还是会 MLE，把 dfs 换成非递归可以通过。

int n,m,id,idx,sm,tt,fa[N],dfn[N],nm[N],rk[N],sz[N];
ll a[N],b[N];
void QwQ() {
    n=rd(),m=rd();
    for(int i=2;i<=n;i++) fa[i]=rd()+1;
    for(int i=1;i<=n;i++) a[i]=rdll(),sz[i]=1;
    for(int i=2;i<=n;i++) a[i]&=a[fa[i]]; 
    for(int i=n;i;i--) sz[fa[i]]+=sz[i];
    for(int i=1;i<=n;i++) dfn[i]=nm[fa[i]]+1,b[dfn[i]]=a[i],rk[dfn[i]]=i,nm[fa[i]]+=sz[i],nm[i]=dfn[i];
    for(int i=1;i<=n;i++) cadd(sm,b[i]%MOD),cadd(tt,vmul(b[i]%MOD,b[i]%MOD));
    wr(vmul(sm,sm)," "),wr(vmul(vsub(vmul(sm,sm),tt),iv),"\n");
    for(int u;m--;) {
        u=rd()+1; ll x=rdll();
        for(int k=0,j;k<60;k++) if(!(x>>k&1)) for(int i=dfn[u];i<dfn[u]+sz[u];i++) {
            if(!(b[i]>>k&1)) {i+=sz[rk[i]]-1; continue;}
            csub(sm,(1ll<<k)%MOD),csub(tt,vmul((1ll<<k)%MOD,vsub(b[i]*2%MOD,(1ll<<k)%MOD))),b[i]-=1ll<<k;
        }
        wr(vmul(sm,sm)," "),wr(vmul(vsub(vmul(sm,sm),tt),iv),"\n");
    }
}