CF1481F

Inui_Sana · 2025-02-07 15:27:33 · 题解

本题解仅为一种线性空间做法的介绍。其他部分不再赘述。

其实就是一个小技巧：线性空间记录 bool 背包每个大小的转移是放入了什么物品。关键在于，注意到对于每个背包大小 x，我们只需要在 dp_{i,x} 第一次为 1 时记录这次转移中放入了什么就行。

这样构造的正确性也相当显然。设上述大小为 x 的背包，放入的物品为 f_i。假设 dp_{i,x} 是从 dp_{i-1,y} 转移过来，那么在更新 f_x，f_y 一定有值，并且以后不再修改。同时 f_x 显然比 f_y 更晚放入背包，所以构造时依次取出的物品不会重复，方案合法。

其实主要还是自己想想才好理解。

然后这个东西也厉害在它可能兼容 bitset 优化 bool 背包。具体地，你只需要将 dp_i 和 dp_{i-1} 的 bitset 异或一下就能得到在 dp_{i,x} 第一次为 1 的 x，然后记录 f_x。由于这样的 x 总共不超过 siz 个，所以配合 _Find_next 相关操作，这一部分总复杂度为 O(siz)，大部分情况下可以接受。

code：

int n,m,dep[N];
pii frm[N];
bool dp[N],ans[N];
vector<int> f[N],g[N],h[N];
int tot,head[N];
struct node{
    int to,nxt;
}e[N];
il void add(int u,int v){
    e[++tot]={v,head[u]},head[u]=tot;
}
void dfs(int u,int f){
    dep[u]=dep[f]+1;
    if(head[u]){
        g[dep[u]].eb(u);
    }else{
        h[dep[u]].eb(u);
    }
    go(i,u){
        int v=e[i].to;
        dfs(v,u);
    }
}
void Yorushika(){
    read(n,m);
    rep(i,2,n){
        int u;read(u);
        add(u,i);
    }
    dfs(1,0);
    rep(i,1,n){
        f[g[i].size()+h[i].size()].eb(i);
    }
    dp[0]=1;
    rep(i,1,n){
        if(f[i].size()){
            int t=f[i].size();
            for(int j=1;j<=t;t-=j,j<<=1){
                drep(k,n,j*i){
                    dp[k]|=dp[k-j*i];
                }
                rep(k,1,n){
                    if(!frm[k].fi&&dp[k]){
                        frm[k]=Mp(i,j);
                    }
                }
            }
            if(t){
                drep(k,n,t*i){
                    dp[k]|=dp[k-t*i];
                }
                rep(k,1,n){
                    if(!frm[k].fi&&dp[k]){
                        frm[k]=Mp(i,t);
                    }
                }
            }
        }
    }
    int mx=0;
    rep(i,1,n){
        mx=max(mx,dep[i]);
    }
    if(dp[m]){
        printf("%d\n",mx);
        int u=m;
        while(u){
            auto [x,y]=frm[u];
            rep(_,1,y){
                if(!f[x].size()){
                    break;
                }
                ans[f[x].back()]=1;
                f[x].pop_back();
            }
            u-=x*y;
        }
        rep(i,1,n){
            pc('a'+!ans[dep[i]]);
        }
    }else{
        printf("%d\n",mx+1);
        bool fl=0;
        int x=m,y=n-x;
        rep(i,1,n){
            if(g[i].size()>x){
                swap(x,y),fl^=1;
            }
            for(int j:g[i]){
                ans[j]=fl;
                x--;
            }
            for(int j:h[i]){
                if(!x){
                    swap(x,y),fl^=1;
                }
                ans[j]=fl;
                x--;
            }
        }
        rep(i,1,n){
            pc('a'+ans[i]);
        }
    }
}
signed main(){
    int t=1;
    //read(t);
    while(t--){
        Yorushika();
    }
}