题解：P13680 [IAMOI R2] 未送出的花

· · 题解

题外话

看到题目描述觉得不对劲，再细看题目背景，咦？

思路

首先有个显然的结论，每个节点的盛开度小于其父节点的盛开度一定不劣。因为如果不然，就可以将两个结点调换位置，此时一定不会有节点的美丽值减少还有可能增加。

因此，我们发现将一个深度为 x 的节点 i 的盛开度设为 y，那么其子树内所有深度为 2\times x-1 和 2\times x 的点 j 的美丽值必然为 y。因为一条链上的美丽度是递减的嘛。设 a_i 为满足条件的 j 的个数。

考虑到每个节点的盛开度小于其父节点的盛开度的限制，我们从 n 到 1 来填数。n 一定要填在 1，之后每个数一定要填在与已填点直接相连的点。假设已经填完了 x 个数，所有已填点的 a_i 相加为 y，那么就表明折下不大于 y 朵花的美丽值不少于 n-x+1。

反着定义动态规划状态，这个就是树上背包了。设 dp_{i_j} 表示以 i 为根的子树内选了 j 个点来填（根必填）所有点的 a_i 之和最多为多少。最后对于每一个 k，查询最小的 dp_{1,m} 使 dp_{1,m}\ge k，输出 n-m+1 即可。

代码

代码运行时间细节 26 毫秒。

评测记录。

#include <bits/stdc++.h>
using namespace std;
typedef int type;
inline type read(){
    type x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(type x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x / 10);
    putchar(x%10+'0');
}
int t,n,dep[10005],f[10005],a[10005],si[100005];
vector<int> v[10005],dp[10005];
void dfs(int p,int fa){
    dep[p]=dep[fa]+1,f[p]=fa;
    for(int i=0;i<v[p].size();i++){
        if(v[p][i]!=fa)dfs(v[p][i],p);
    }
}
int qiu(int p,int fa,int x,int y){
    int ret=0;
    if(dep[p]==x||dep[p]==y)ret++;
    else if(dep[p]>x&&dep[p]>y)return ret;
    for(int i=0;i<v[p].size();i++){
        if(v[p][i]!=fa)ret+=qiu(v[p][i],p,x,y);
    }
    return ret;
}
void cha(int p,int fa){
    si[p]=1;
    dp[p].push_back(0),dp[p].push_back(a[p]);
    for(int i=0;i<v[p].size();i++){
        if(v[p][i]!=fa){
            cha(v[p][i],p);
            while(dp[p].size()<=si[p]+si[v[p][i]])dp[p].push_back(0);
            for(int j=si[p];j>=1;j--){
                for(int k=0;k<=si[v[p][i]];k++){
                    dp[p][j+k]=max(dp[p][j+k],dp[p][j]+dp[v[p][i]][k]);
                }
            }
            si[p]+=si[v[p][i]];
        }
    }
}
signed main() {
    t=read();
    while(t--){
        n=read();
        for(int i=1;i<=n-1;i++){
            int x,y;
            x=read(),y=read();
            v[x].push_back(y);
            v[y].push_back(x);
        }
        dfs(1,0);
        for(int i=1;i<=n;i++)a[i]=qiu(i,f[i],dep[i]*2-1,dep[i]*2);
        cha(1,0);
        for(int i=1;i<=n;i++){
            int l=1,r=n,mid,ret;
            while(l<=r){
                mid=(l+r)/2;
                if(dp[1][mid]>=i)ret=mid,r=mid-1;
                else l=mid+1;
            }
            write(n-ret+1),putchar(' ');
        }
        putchar('\n');
        for(int i=1;i<=n;i++)v[i].clear(),dp[i].clear();
    }
    return 0;
}