P13680 题解

Melo_qwq · 2025-08-12 14:59:22 · 题解

感觉非常牛的一道题！

首先给出结论：整棵树盛开度的最优形态一定是一个大根堆。

考虑使用调整法，假设现在有一个儿子的盛开度大于父亲的盛开度，现在尝试交换儿子和父亲的盛开度：

• 对于儿子的子树中的节点，根到它们的路径的盛开度序列不变，美丽值不发生变化。
• 对于父亲子树中且非儿子子树中的节点，根到它们的路径只经过父亲而不经过那个儿子，所以盛开度序列中有且仅有一个数会变大，美丽值不降。
• 对于非父亲子树中的节点，没有变化。

所以此时交换儿子和父亲一定不劣，得证。

那么我们可以知道，一个点 u 的美丽值就是根到它的路径上第 \lceil\frac{dep_u}{2}\rceil 个点的盛开度，dep_u 表示深度。

那么对于每个点，我们可以求出它被作为美丽值的次数，记为 cnt_i，这个用倍增可以做到 \Theta(n\log n)，不再赘述。

现在考虑，假如给定了每个节点的盛开度和 k，该如何求出答案？

显然是应该按照盛开度从大到小枚举所有的点，并且累加 cnt，直到 cnt\ge k 的时候结束，答案就是最后一个点的盛开度。

观察上述过程，不难发现盛开度从大到小排序后，一段前缀盛开度对应的点构成一个包含 1 号点的联通块。

那么本题的问题可以转化为对于 k\in[1,n]，求一个包含 1 号点的联通块，满足这个联通块的 \sum cnt_i\ge k，同时联通块的点数最小。

这个等价于求包含 1 号点的，大小为 1,2\cdots n 的联通块的 cnt 之和最大能到多少。

这是可以树形 DP 的，如果要构成一个联通块，那么如果我们不选点 u 那么 u 的子树中的点都不能选。

一个有限制的背包问题。

考虑拍到 DFS 序上，再把整个 DFS 序列翻转过来，那么第 i 个点的子树区间就是 [i-siz_{id_i}+1,i]，其中 id_i=j 表示 DFS 序为 i 的点是 j，siz 表示子树大小。

那么设 dp_{i,j} 表示枚举到第 i 个点，选了 j 个，cnt 之和的最大值。

• 如果选 i，那么 dp_{i,j}=\max(dp_{i,j},dp_{i-1,j-1}+cnt_{id_i})。
• 否则 dp_{i,j}=\max(dp_{i,j},dp_{i-siz_{id_i},j})。

就做完了。

总体复杂度 \Theta(n^2)，瓶颈在 DP。

Code

inline void dfs (int cur ,int faa) {
    id[++ dfn] = cur ;
    fa[cur][0] = faa ;
    dep[cur] = dep[faa] + 1 ;
    siz[cur] = 1 ;
    f (i ,1 ,20 ,1) fa[cur][i] = fa[fa[cur][i - 1]][i - 1] ;
    for (int i = head[cur] ; i ; i = e[i].nxt) {
        int nex = e[i].to ;
        if (nex == faa) continue ;
        dfs (nex ,cur) ;
        siz[cur] += siz[nex] ;
    }
    int len = dep[cur] - ((dep[cur] + 1) >> 1) ;
    int u = cur ;
    f (i ,0 ,20 ,1) {
        if (len & (1 << i)) u = fa[u][i] ;
    } cnt[u] ++ ;
}

int main () {
    read (t) ;
    while (t --) {
        f (i ,1 ,n ,1) {
            head[i] = cnt[i] = 0 ;
            f (j ,1 ,i ,1) dp[i][j] = 0 ;
        }
        f (i ,1 ,n ,1) f (j ,0 ,20 ,1) fa[i][0] = 0 ; 
        tot = dfn = 0 ;
        read (n) ;
        f (i ,1 ,n - 1 ,1) {
            int u ,v ; read (u ,v) ;
            add (u ,v) ,add (v ,u) ;
        } dep[1] = 1 ;
        dfs (1 ,0) ;
        std :: reverse (id + 1 ,id + dfn + 1) ;
        f (i ,1 ,n ,1) {
            f (j ,1 ,i ,1) {
                dp[i][j] = std :: max (dp[i][j] ,dp[i - 1][j - 1] + cnt[id[i]]) ;
                dp[i][j] = std :: max (dp[i][j] ,dp[i - siz[id[i]]][j]) ;
            }
        }
        f (i ,1 ,n ,1) {
            int loc = std :: lower_bound (dp[n] + 1 ,dp[n] + n + 1 ,i) - dp[n] ;
            std :: cout << n - loc + 1 << " \n"[i == n] ;
        }
    }
    return 0 ;
}