「题解」P9655 『GROI-R2』 Beside You

do_while_true · 2023-09-23 19:26:26 · 题解

是不是爆标了啊/yiw。

把每个点权值 a_x ( 看成 -1。) 看成 1。首先得到一个简单的 \mathcal{O}(n^2) dp。f_{x,i} 表示 x 子树内到 x 前缀和为 i 的最多点数。如果 a_x=1 对于儿子 v 那么 f_{x,i+1}\gets f_{x,i+1}+f_{v,i}。否则 f_{x,i-1}\gets f_{x,i-1}+f_{v,i}。最后再将 f_x 中有值的加上 1（也就是存在这种方案就把 x 这个点算上）。如果 a_x=1 且 f_{x,1} 没值那么把 f_{x,1} 设为 1。

template<typename T>T cmax(T &x, T y){return x=x>y?x:y;}
void dfs(int x,int fa){
    len[x]=1;
    for(auto v:eg[x])if(v!=fa){
        dfs(v,x);
        cmax(len[x],len[v]+1);
        if(a[x]==1){
            for(int i=0;i<=len[v];i++)
                f[x][i+1]+=f[v][i];
        }
        else{
            for(int i=1;i<=len[v];i++)
                f[x][i-1]+=f[v][i];
        }
    }
    for(int i=0;i<=len[x];i++)if(f[x][i])++f[x][i];
    if(a[x]==1&&!f[x][1])f[x][1]=1;
    cmax(ans,f[x][0]);
}

尝试长剖优化。首先是后缀非零位置加这个东西。可以再记一个 t_{x,i} 表示要将 f_{x,\geq i} 的非零位置加上 t_{x,i}。需要用到 f 真实值的时候去更新（用多少更新多少）。也就是在短儿子往自己合并的时候把短儿子更新掉。也把自己用到的 f 更新掉。然后轻儿子再合并上来。