AC466A 2024省选联测19 寄（post）

题意

一棵有边权的树，给定 \(m\) 个关键点，让你选择若干个点，使得每个关键点到你选择的点的距离的最小值之和加上选择的点的个数乘 \(C\) 最小。

求这个最小值。

\(n \le 3000\)

Sol

考虑将选择点的个数扔掉，直接考虑对于每个点加上 \(C\) 的贡献。

设 \(f_{i, j}\) 表示 \(i\) 的贡献点为 \(j\)，\(i\) 子树内所有点的贡献。

考虑转移，注意到一个贡献点所贡献到的关键点一定形成一个连通块，所以只需要考虑当前点与儿子的关键点相同即可。

设 \(f_{i, 0}\) 表示 \(min_{j = 1} ^ {n} f_{i, j}\)。

可得：

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <cmath>
#include <tuple>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(int x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
const int N = 3e3 + 5, M = 6e3 + 5, inf = 2e18;

namespace G {

array<int, N> fir;
array<int, M> nex, to, len;

int cnt = 1;

void add(int x, int y, int z) {
    cnt++;
    nex[cnt] = fir[x];
    to[cnt] = y;
    len[cnt] = z;
    fir[x] = cnt;
}

}  // namespace G

namespace Esl {

array<int, M> idx, dfn;
array<int, N> fa, dep, dis;
int cnt;

void dfs(int x) {
    cnt++;
    dfn[x] = cnt;
    idx[cnt] = x;
    for (int i = G::fir[x]; i; i = G::nex[i]) {
        if (G::to[i] == fa[x])
            continue;
        fa[G::to[i]] = x;
        dep[G::to[i]] = dep[x] + 1;
        dis[G::to[i]] = dis[x] + G::len[i];
        dfs(G::to[i]), cnt++, idx[cnt] = x;
    }
}

array<array<int, 22>, M> sT;
array<int, M> lg;

void init() {
    for (int i = 1; i <= cnt; i++) lg[i] = log2(i);
    for (int i = 1; i <= cnt; i++) sT[i].fill(inf);
    for (int i = 1; i <= cnt; i++) sT[i][0] = dfn[idx[i]];
    for (int j = 1; j < 21; j++)
        for (int i = 1; i + (1 << j) - 1 <= cnt; i++)
            sT[i][j] = min(sT[i][j - 1], sT[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r) {
    tie(l, r) = minmax(dfn[l], dfn[r]);
    int len = lg[r - l + 1];
    return idx[min(sT[l][len], sT[r - (1 << len) + 1][len])];
}

}  // namespace Esl

array<array<int, N>, N> f;
array<int, N> val;

int dist(int x, int y) { return Esl::dis[x] + Esl::dis[y] - 2 * Esl::dis[Esl::query(x, y)]; }

void dfs(int x, int n, int C) {
    for (int i = 1; i <= n; i++) {
        f[x][i] = C + val[x] * dist(x, i);
        /* write(x), putchar(32); */
        /* write(i), putchar(32); */
        /* write(dist(x, i)), puts("@"); */
    }
    for (int i = G::fir[x]; i; i = G::nex[i]) {
        if (G::to[i] == Esl::fa[x])
            continue;
        dfs(G::to[i], n, C);
        for (int j = 1; j <= n; j++) f[x][j] += min(f[G::to[i]][j] - C, f[G::to[i]][0]);
    }
    f[x][0] = inf;
    for (int i = 1; i <= n; i++) f[x][0] = min(f[x][i], f[x][0]);
}

signed main() {
    freopen("post.in", "r", stdin);
    freopen("post.out", "w", stdout);
    int n = read(), m = read(), C = read();
    for (int i = 2; i <= n; i++) {
        int x = read(), y = read(), z = read();
        G::add(x, y, z), G::add(y, x, z);
    }
    for (int x; m--;) x = read(), val[x]++;
    Esl::dfs(1), Esl::init();
    dfs(1, n, C);
    write(f[1][0]), puts("");
    return 0;
}