【题解】CF2138C1 Maple and Tree Beauty (Easy Version)

· · 题解

最长公共子序列看起来很唬人，实际想一想就能知道最优方案一定是把最长公共子序列摆在从根下来连续的一根链上，这样能使每个 0/1 被利用的程度最大。

考虑二分深度，接下来的问题变成了一个背包：每个深度的点必须染同一种颜色，要求最后恰好能有 k 个点染成同一种颜色。

考虑到这个背包里所有的物品重量之和 \leq n ,所以不同重量的物品的级别是 \sqrt{n} ,合并相同重量物品，用位优化的多重背包处理即可。可以上 bitset 优化，复杂度为 O(\frac{n logn \sqrt{n}} {w} )。

贴上很丑的代码：

#include<bits/stdc++.h>
#define N 200010
using namespace std;
int T,n,k,dep[N],buc[N],a[N],tn,s[N],b[N],deg[N];
bitset<N> f,g,ttt;
bool check(int x) {
    f.reset(),f[0]=1,tn=0;int sum=0;
    for(int i=1; i<=x; i++) b[i]=buc[i],sum+=b[i];
    sort(b+1,b+x+1);
    for(int i=1; i<=x; i++) {
        if(b[i]!=b[i-1]) a[++tn]=b[i],s[tn]=1;
        else s[tn]++;
    }
    for(int i=1; i<=tn; i++) {
//      cout<<a[i]<<" "<<s[i]<<endl;
        for(int t=20; t; t--) if((1<<t)-1<=s[i]) {
            s[i]-=(1<<t)-1;
            for(int j=0; j<t; j++) f|=f<<((1<<j)*a[i]);
            break;
        }
        if(s[i]) f|=f<<(s[i]*a[i]);
    }
    g=f&ttt;
    if(sum+k-n>=0) g=g>>(sum+k-n);
    return g.count();
}
void solve() {
    cin>>n>>k;
    for(int i=1; i<=n; i++) dep[i]=buc[i]=deg[i]=0;
    dep[1]=1,buc[1]=1;int mx=0x3f3f3f3f;
    for(int i=2; i<=n; i++) {
        int fa; cin>>fa;
        dep[i]=dep[fa]+1,buc[dep[i]]++,deg[fa]++;
    }
    for(int i=1; i<=n; i++) if(!deg[i]) mx=min(mx,dep[i]);
    ttt.reset();
    for(int i=0; i<=k; i++) ttt[i]=1;
    int l=1,r=mx,ans=0;
//  cout<<mx<<endl;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(check(mid)) ans=max(ans,mid),l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<endl;
}
int main() {
    cin>>T;
    while(T--) solve();
}