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

· · 题解

思路

考虑盛开度已经确定后，对于一个点 u 到点 1 路径上两个节点盛开度 x,y(x<y)，交换此处两盛开度对于点 u 的美丽度没有影响，同时如果 x 的节点比 y 的节点高，交换它们一定不劣。

同上，考虑一种情况，盛开度 x 的位置到盛开度 y 父节点间有任意分支，交换 x,y 后，这些分支上的点到点 1 路径上点的盛开度集合中的一个元素被替换为一个更大的数，同时盛开度 y 的点及其子树内不受影响。

于是有性质，父节点盛开度大于子节点盛开度更优。据此，如果一个节点深度为 d，那么它的美丽度由它到点 1 路径上深度为 \lceil\frac{d}{2}\rceil 的节点的盛开度确定。

我们可以知道每个点的盛开度确定多少个点的美丽度，题目相当于求与点 1 相连最小联通块满足美丽度确定点的个数大于等于 k。

树上背包即可，令 f_{u,i} 表示 u 子树内包含 u 的大小 i 的联通块美丽度确定点数最大值，转移显然：

\large f_{fa_u,i+j}=\max(f_{fa_u,i+j},f_{fa_u,i}+f_{u,j})

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,p[N],siz[N],son[N],F[N],f[N][N];
int head[N],vi[N<<1],nxt[N<<1],tot;
inline void add(int u,int v){
    vi[++tot]=v;nxt[tot]=head[u];head[u]=tot;
    vi[++tot]=u;nxt[tot]=head[v];head[v]=tot;
    return;
}
inline void dfs(int u,int fa,int dep){
    p[dep]=u;
    son[p[dep/2]]++;
    for(int i=head[u];i;i=nxt[i]){
        int v=vi[i];
        if(v==fa)continue;
        dfs(v,u,dep+1);
    }
    return;
}
inline void dp(int u,int fa){
    siz[u]=1;
    f[u][1]=son[u];
    for(int i=head[u];i;i=nxt[i]){
        int v=vi[i];
        if(v==fa)continue;
        dp(v,u);
        for(int j=siz[u]+siz[v];j>siz[u];j--)f[u][j]=0;
        for(int j=1;j<=siz[u];j++)F[j]=f[u][j];
        for(int j=1;j<=siz[u];j++)
        for(int k=1;k<=siz[v];k++)
            f[u][j+k]=max(f[u][j+k],F[j]+f[v][k]);
        siz[u]+=siz[v];
    }
}
inline void solve(){
    n=read();
    tot=0;
    for(int i=1;i<=n;i++)
        head[i]=son[i]=0;
    for(int i=1;i<n;i++)add(read(),read());
    dfs(1,0,0);
    dp(1,0);
    for(int i=1;i<=siz[1];i++)
    for(int j=f[1][i-1]+1;j<=f[1][i];j++)
        printf("%d ",n-i+1);
    puts("");
    return;
}
int main(){
//  freopen("c.in","r",stdin);
//  freopen("c.out","w",stdout);
    int t=read();
    while(t--)solve();
    return 0;
}