本文共 2358 字，大约阅读时间需要 7 分钟。

题目

题目概要
给定一个正整数系数的 $k$ 次函数 $c(x)$ 表示度数为 $x$ 的节点权值。求构建一棵树，使得权值和最大。

数据范围与约定
$n\le 3000,k\le 10$ 。

思路

考虑要构建一棵树，$\text{prufer}$ 序列会是一个不错的选择。

根据 $\text{prufer}$ 的性质，每个点出现的次数为度数减 $1$ ，并且总序列长度为 $n-2$ 。

发现权值与节点编号无关。于是可以当成做一个 完全背包（往 $\text{prufer}$ 序列里赛点）：度数为 $x$ 的点，体积是 $x-1$ ，权值是 $c(x)$ 。

我们还得要求背包内物品的数量恰好为 $n$ ——表示 $n$ 个点的度数都被考虑了。

没有关系！我们有体积为 $0$ 的物品，可以随便填。体积为 $0$ 的不能用普通的背包进行转移，必须特殊考虑。

有一个方法：开始时把 $n$ 个体积为 $0$ 的物品放进背包，然后剩下的过程就是每次将若干个体积为 $0$ 的物品替换为体积为 $x$ 的物品。即 $f_0=n\cdot c(1)$ 。

不仅解决了 $0$ 的问题，顺便还保证了背包内恰好有 $n$ 个物品。真好啊 😂

会不会替换过多？不会。因为体积不为 $0$ 的物品，根本放不了 $n$ 个。

那么 $$f_x=\underset{2\le j\le x+1}{\max }\left[f_{x-(j-1)}+c(j)-c(1)\right]$$

但是本题还要输出方案。这就要求 $dp$ 的时候记录转移的前驱。利用这个我们可以计算出最终的树上的 $n$ 个点在 $\text{prufer}$ 序列上出现次数。

然后利用这个贪心的思想构建这棵树（度数越小的放末尾，事实证明，把所有叶子结点放在末尾即可），注意根的特殊性（对于非根节点，在 $\text{prufer}$ 序列出现次数 $=$ 儿子数；对于根，在 $\text{prufer}$ 序列出现次数 $=$ 儿子数 $-1$ ）。

复杂度 $\mathcal{O}(n^2)$ 。

#include <bits/stdc++.h>using namespace std;const int N = 3005, mod = 59393;int n, k, tot, a[N], c[N], f[N], g[N], d[N];void dfs (int x) {       for (int i = 1; i <= d[x]; ++i) {           printf("%d %d\n", x, ++tot);        dfs(tot);    }}int main () {       scanf("%d%d", &n, &k);    for (int i = 0; i <= k; ++i) {           scanf("%d", &a[i]);    }    for (int i = 0; i <= n; ++i) {           for (int j = k; ~j; --j) {               c[i] = c[i] * i % mod + a[j];            c[i] %= mod;        }    }    if (n == 1) {           printf("0 %d\n", c[0]);        return 0;    }    if (n == 2) {           printf("1 %d\n",2 * c[1]);        printf("1 2\n");        return 0;    }    f[0] = n * c[1];    for (int i = 2; i <= n; ++i) {           for (int j = i - 1; j <= n - 2; ++j) {               if (f[j] < f[j - (i - 1)] + c[i] - c[1]) {                   f[j] = f[j - (i - 1)] + c[i] - c[1];                g[j] = j - (i - 1);            }        }    }    printf("%d %d\n", n - 1, f[n - 2]);    for (k = n - 2; k; k = g[k]) {           d[++d[0]] = k - g[k];    }    sort(d + 1, d + d[0] + 1);    ++d[1];    dfs(tot = 1);    return 0;}

鸣谢

感谢提供了思路和代码。果然我是个动态规划的矮子