题解：CF2138C1 Maple and Tree Beauty (Easy Version)

z__ql_999 · 2025-09-12 15:41:15 · 题解

做过的最简单的E。

solution

转化一下题意，可以发现，就是对树的每一层进行染色，要求颜色相同的层数最多。

那么我们显然有 O(n^3) 的dp，设 dp_{i,j,k} 表示考虑到深度为 i 的层，用了 j 个 1 和 k 个 0。贪心地，容易发现，先涂结点少的层显然比涂结点多的层优，这样可以节省一些颜色。

于是我们先进行一遍bfs分层，记录每层结点数 num_i，再按结点数从小到大排序，将三维dp压成二维，因为这样不会有空下不选的情况。

设 dp_{i,j} 表示考虑到深度为 i 的层，用了 j 个 1，再顺便维护前 i 层结点总数，记为 cnt，cnt-j 即可得到已用的 0 数量。

转移时要判断 0 和 1 的数量有没有超过总数。

dp转移式：dp_{i,j}=\max(dp_{i-1,j-num_i}+1,dp_{i-1,j}+1)。

时间复杂度 O(n^2)。

C1 code

C2

数据范围 n=2\times10^5 很难不想到bitset优化。用bitset的第 i 位表示：考虑到当前这一层(都填满），用了 i 个 1，存不存在合法方案。同样要考虑 0 和 1 数量限制。

int p=(cnt<=n-k?dp._Find_first():dp._Find_next(cnt-n+k-1));

解释一下，如果 0 数量够，找个用 1 最少的（更有可能符合条件）。否则先用最多的 0，找个用 1 最少的。如果找得到，说明这一层能被填满，答案加一。

code

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int dis[N],num[N];
vector<int> a[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k,ans=0,maxx=1,cnt=0,minn=1e9;
        bitset<N> dp;
        cin>>n>>k;
        for(int i=2;i<=n;i++){
            int v;
            cin>>v;
            a[i].push_back(v),a[v].push_back(i);
        }
        queue<int> q;
        q.push(1);
        dis[1]=1;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            num[dis[u]]++,maxx=max(maxx,dis[u]);
            if(a[u].size()==1&&dis[a[u][0]]) minn=min(minn,dis[u]);
            for(auto v:a[u]){
                if(dis[v]) continue;
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
        maxx=min(maxx,minn);
        sort(num+1,num+maxx+1);
        dp[0]=1;
        for(int i=1;i<=maxx;i++){
            cnt+=num[i];
            dp|=dp<<num[i];
            int p=(cnt<=n-k？dp._Find_first():dp._Find_next(cnt-n+k-1));
            if(p<=k) ans++;
        }
        cout<<min(ans,maxx)<<"\n";
        for(int i=0;i<=n;i++) dis[i]=num[i]=0,a[i].clear();
    }
    return 0;
}