题目链接：Codeforces 70E

虽然已经是二十一世纪了，但是大众传媒在海象国并不普及，城市之间只能通过公路交流。海象国中任意两座城市之间有且只有一条路径，且每条道路的长度都是 $1$。

为了进行改革，将会选择一些城市作为信息中心，维护一个信息中心需要 $k$ 元钱。对于其他城市，他们将会从最近的信息中心获得消息，如果设两者直接的距离为 $len$，那么这将花费 $d_{len}$ 元钱。

请你求出一种方案使得花费最小，并求出每个城市会从哪个信息中心获得消息。

数据范围：$1\le n\le 180$，$1\le k\le 10^5$，$0\le d_i\le d_{i+1}\le 10^5$。

Solution

首先我们用 $\text{Floyd}$ 求出任意两个点之间的距离，记为 $dis(i,j)$。

考虑 $\text{DP}$ 状态：设 $f(i,j)$ 表示在第 $i$ 个点建立信号站使得 $j$ 子树内获得信号的最小代价。

如果我们只考虑 $u$ 点本身，那么有 $f(i,u)=d_{dis(i,u)}+k$。假设我们已经求出了子树 $v$ 的 $\text{DP}$ 值：

• 假设 $v$ 点也从 $i$ 的位置获得信号，由于 $u,v$ 两点重复考虑了 $k$ 的代价，那么子树 $v$ 对子树 $u$ 的贡献为 $f(i,v)-k$。
• 假设 $v$ 点不建造在 $i$ 点，那么对 $u$ 子树的贡献为 $\min_{1\le j\le n}\{f(j,v)\}$。我们记使得 $f(i,u)$ 最小的 $i$ 为 $p(u)$。那么可以 $O(1)$ 得到贡献值。

最后如何计算答案？我们记点 $i$ 从点 $ans(i)$ 获得信号，那么我们只需要比较 $f(p(v),v)$ 和 $f(ans(u),v)-k$ 的值就可以得到 $ans(v)$ 的值。递归计算即可。

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

Code

#include <cstdio>
#include <algorithm>

const int N = 205, M = 405;

int n, k, tot, d[N], e[N][N], lnk[N], ter[M], nxt[M];
int dis[N][N], f[N][N], p[N], ans[N];

void add(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
void Floyd() {
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}
void dfs(int u, int fa) {
    for (int i = 1; i <= n; i++) {
        f[i][u] = d[dis[i][u]] + k;
    }
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == fa) continue;
        dfs(v, u);
        for (int i = 1; i <= n; i++) {
            f[i][u] += std::min(f[p[v]][v], f[i][v] - k);
        }
    }
    p[u] = 1;
    for (int i = 1; i <= n; i++) {
        if (f[i][u] < f[p[u]][u]) p[u] = i;
    }
}
void getPath(int u, int fa, int pos) {
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == fa) continue;
        ans[v] = (f[p[v]][v] > f[pos][v] - k ? pos : p[v]);
        getPath(v, u, ans[v]);
    }
}
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        scanf("%d", &d[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dis[i][j] = (i == j ? 0 : 0x3f3f3f3f);
        }
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        dis[u][v] = dis[v][u] = 1;
        add(u, v), add(v, u);
    }
    Floyd();
    dfs(1, 0);
    printf("%d\n", f[p[1]][1]);
    ans[1] = p[1];
    getPath(1, 0, ans[1]);
    for (int i = 1; i <= n; i++) {
        printf("%d%c", ans[i], " \n"[i == n]);
    }
    return 0;
}