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

· · 题解

算半个验题人写写题解。

思路

不难发现父亲的盛开度大于儿子，证明可以考虑交换两个的盛开度，发现只会让所有美丽值不降。

然后就能发现中位数的条件是假的，一朵花的美丽值就是它 \dfrac{dep}{2} 辈祖先的盛开度。我们预处理出每朵花被当做 \dfrac{dep}{2} 辈祖先多少次，令它为 a_u，那么他的盛开度就会在最终的美丽值序列里出现 a_i 次。

于是我们发现，相当于我们每次要求小的与根相连的连通块，满足它们的 a 之和大于等于 k 即可。

考虑 dp。令 f_{i,j} 表示和点 i 相连的 a 之和为 j 的最小连通块大小。转移有：

f_{u,i}=\min\{f_{u,i},f_{u,j}+f_{v,i-j}\}

初始化 f_{u,a_u}=1。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
const int M=2e4+5;
int t,n,u,v,cnt,top,a[N],s[N],siz[N],to[M],nxt[M],h[N],f[N][N],g[N];
void save(int u,int v){
    to[++cnt]=v;
    nxt[cnt]=h[u];
    h[u]=cnt;
}
void dfs(int u,int fa){
    s[++top]=u;
    a[s[(top+1)/2]]++;
    for(int i=h[u];i;i=nxt[i]){
        if(to[i]==fa) continue;
        dfs(to[i],u);
    }
    top--;
}
void dfs2(int u,int fa){
    siz[u]=a[u];
    f[u][a[u]]=1;
    for(int i=h[u];i;i=nxt[i]){
        if(to[i]==fa) continue;
        dfs2(to[i],u);
        memcpy(g,f[u],sizeof(g));
        for(int j=0;j<=siz[u];j++) for(int k=0;k<=siz[to[i]];k++) f[u][j+k]=min(f[u][j+k],g[j]+f[to[i]][k]);
        siz[u]+=siz[to[i]];
    }
}
void clear(){
    for(int i=1;i<=n;i++) a[i]=h[i]=0;
    cnt=top=0;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<n;i++){
            scanf("%d%d",&u,&v);
            save(u,v);
            save(v,u); 
        }
        for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j]=1e9;
        dfs(1,0);
        dfs2(1,0);
        for(int i=n-1;i>=1;i--) f[1][i]=min(f[1][i],f[1][i+1]);
        for(int i=1;i<=n;i++) printf("%d ",n-f[1][i]+1);
        printf("\n");
        clear();
    }
    return 0;
}