题目链接：LOJ 6395

经过选拔，Kiana 成为了可乐城的市长，为了兑现选举承诺，她决定在可乐城的 $n$ 个重要地标之间修建地铁。

可乐城的交通状况并不复杂，在任意两个地标之间修建一条地铁轨道都是可行的，但是地铁轨道并不是越多越好，如果有太多地铁从一个地标处经过，该地标的拥堵程度将大幅增加。为此，Kiana 决定给每个地标一个便利度来衡量拥堵程度，如果有 $d$ 条地铁轨道经过了某个地标，那么该地标的便利度为 $f(d) \bmod 59393$，其中 $f(x) = \sum_{i = 0} ^ {k} a_i x ^ i$ 是 Kiana 指定的一个 $k$ 次多项式。

因为修建地铁有一定的成本，所以 Kiana 希望新建的地铁轨道尽可能少，但任意两座地标之间都需要能通过地铁相互到达。Kiana 想知道在给定的条件下，什么样的修建方案可以使得地标的便利度之和最大。由于她不会做，所以希望你来告诉她答案。

数据范围：$1 \le n \le 3000$，$1 \le k \le 10$，$0 \le a_i \le 50$。

Solution

考虑 Prufer 序列，$f(i, j)$ 表示考虑了前 $i$ 个点，当前 Prufer 序列的长度为 $j$，那么有转移 $f(i, j) = \max \{ f(i - 1, j - k) + f(k + 1)\}$，预处理出所有 $f(x)$ 后 $\mathcal O(1)$ 转移。

最后根据 Prufer 序列还原出原树。

时间复杂度：$\mathcal O(n ^ 2)$。

Code

#include <bits/stdc++.h>

const int N = 3e3, K = 10, MOD = 59393;
int n, k, a[K + 5], f[N + 5], pre[N + 5], w[N + 5], deg[N + 5];

inline int calc(int x) {
    int ans = 0;
    for (int i = k; i >= 0; i--) {
        ans = (ans * x + a[i]) % MOD;
    }
    return ans;
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i <= k; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; i++) {
        w[i] = calc(i);
    }
    if (n == 1) {
        printf("0 %d\n", a[0]);
        return 0;
    }
    if (n == 2) {
        printf("1 %d\n1 2\n", w[1] * 2);
        return 0;
    }
    std::fill(f + 1, f + n - 1, INT_MIN);
    f[0] = w[1] * n;
    for (int i = 1; i <= n - 2; i++) {
        for (int j = 1; j <= i; j++) {
            if (f[i] < f[i - j] + w[j + 1] - w[1]) {
                f[i] = f[i - j] + w[j + 1] - w[1];
                pre[i] = j;
            }
        }
    }
    std::vector<int> prufer;
    for (int i = 1, k = n - 2; k > 0; i++) {
        for (int j = 1; j <= pre[k]; j++) {
            prufer.push_back(i);
        }
        deg[i] = pre[k];
        k -= pre[k];
    }
    printf("%d %d\n", n - 1, f[n - 2]);
    std::set<int> set;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            set.insert(i);
        }
    }
    for (auto u : prufer) {
        printf("%d %d\n", u, *set.begin());
        set.erase(set.begin());
        if (--deg[u] == 0) {
            set.insert(u);
        }
    }
    printf("%d %d\n", *set.begin(), *set.rbegin());
    return 0;
}