题解：P6419 [COCI2014-2015#1] Kamp

· · 题解

P6419 [COCI2014-2015#1] Kamp

本题大部分人都是换根 \text{DP} 的做法，我有一种不需要 \text{DP} 的做法，想要分享一下。

题意

给定一棵 n 个节点的树，包含 k 个关键点，求从节点 1 \dots n 出发，走遍 k 个关键点所需走的最小长度。

前置知识

如果你做过 [SDOI2015] 寻宝游戏，或者说你学过虚树，你就会知道有这样一个重要的性质：

在一棵树上有 n 个关键点 u_{1 \dots n}，不妨断言其顺序已经按照 \text{DFN} 序升序排列，则这 n 个点的极小联通子树的边权和 S 满足：

S = \frac{1}{2} \sum_{x = 1} ^ n \operatorname{dis}(u_i, u_{i + 1})

特别的，规定 u_{n + 1} = u_1。

证明其实很简单。回顾 \text{DFS} 的过程，会发现 \text{DFS} 的过程刚好就是从 u_i 不断跳转到 u_{i + 1} 的过程！

而在 \text{DFS} 中，每条边被统计了两边（入一遍，出一遍），因此总和的一半即为极小联通子树的边权和。

问题分析

认真思考原问题，不难发现节点 u 的最小值值就是 u 和 关键点组成的，以 u 为根节点的，最小联通子树的大小 - u 到关键点的最大距离。

推导是显然的，原问题就是一个 \text{DFS}，只不过允许结束时不在根节点 u。因此只要结束时处于距离 u 最远的点就可以最小化答案。

约定 D = 2S = \sum_{x = 1} ^ n \operatorname{dis}(u_i, u_{i + 1})：

考虑先来求 u 和 关键点组成二倍最小联通子树的大小 D_0：

我们可以先求关键点组成最小联通子树，然后考虑插入一个点 u。

D_u = D_0 - \operatorname{dis}(\operatorname{P}(u), \operatorname{N}(u)) + \operatorname{dis}(\operatorname{P}(u), u) + \operatorname{dis}(u, \operatorname{N}(u))

规定点集以 \text{DFN} 序升序排列，则 P(u) 为 u 的前驱，N(u) 为 u 后继。

则可以轻松地用 D_0 推出所有的 D_u

实现时，可以二分点集，也可以直接枚举 \text{DFN} 序列。

接下来，我们要求 u 到关键点集合的最长距离。

一开始我思维太僵化，没想出来怎么求，故发 讨论版 讨论做法。

@小粉兔 提出了一个简单的做法，在这里拜谢粉兔：

然后，$O(1)$ 求树上两点距离 / LCA 是熟知的。

当然，利用 \pm 1 \ \text{RMQ} 来求 \text{LCA} 比较麻烦（其实就是我不会写），因此我选择树剖神教。实际最大点 377 ms，和 O(n) 的 \text{DP} 差不多。

代码

轻度压行，不过写的还算清晰。

#include <bits/extc++.h>

#define inline __always_inline
template <typename T> inline void read(T &x)
{
    char ch;
    for (ch = getchar(); !isdigit(ch); ch = getchar());
    for (x = 0; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
const int MaxN = 5e5 + 5, MaxK = MaxN;

struct edge_t { int v, w; };
std::vector<edge_t> graph[MaxN];
inline void add_edge(int u, int v, int w) { graph[u].push_back({v, w}), graph[v].push_back({u, w}); }
int n, k, u, v, w, x[MaxN];
int parent[MaxN], head[MaxN], hson[MaxN];
int depth[MaxN], size[MaxN], dfn[MaxN], map[MaxN], cur = 1;
int64_t sum[MaxN], max[MaxN];
void build(int u)
{
    size[u] = 1;
    for (auto &&[v, w] : graph[u])
        if (v != parent[u])
        {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            sum[v] = sum[u] + w;
            build(v);
            size[u] += size[v];
            if (size[hson[u]] < size[v]) hson[u] = v;
        }
}
void decomposition(int u, int h)
{
    map[dfn[u] = cur++] = u;
    head[u] = h;
    if (hson[u]) decomposition(hson[u], h);
    for (auto &&[v, w] : graph[u])
        if (v != parent[u] && v != hson[u])
            decomposition(v, v);
}
int LCA(int u, int v)
{
    while (head[u] != head[v])
    {
        if (depth[head[u]] < depth[head[v]]) std::swap(u, v);
        u = parent[head[u]];
    }
    return depth[u] < depth[v] ? u : v;
}
inline int64_t dis(int u, int v)
{
    int lca = LCA(u, v);
    return sum[u] + sum[v] - sum[lca] * 2;
}
auto cmp = [](int x, int y) { return dfn[x] < dfn[y]; };
int64_t d[MaxN]; char key[MaxN];
int p, q;
void dfs(int u, int parent)
{
    for (auto &&[v, w] : graph[u])
        if (v != parent)
        {
            d[v] = d[u] + w;
            if (key[v] && d[p] < d[v]) p = v;
            dfs(v, u);
        }
}
int64_t D[MaxN];
int main()
{
    read(n), read(k);
    for (int i = 1; i < n; i++)
        read(u), read(v), read(w), add_edge(u, v, w);
    build(1), decomposition(1, 1);
    for (int i = 1; i <= k; i++) read(x[i]), key[x[i]] = 1;
    dfs(x[1], 0), q = p, dfs(q, 0);     // 寻找距离最远的两点。
    for (int i = 1; i <= n; i++)
        max[i] = std::max(dis(i, p), dis(i, q));
    std::sort(x + 1, x + k + 1, cmp);
    x[0] = x[k], x[k + 1] = x[1];       // 添加哨兵，简化边界处理
    for (int i = 1; i <= k; i++) D[0] += dis(x[i], x[i + 1]);
    for (int i = 1, id = 1; i <= n; i++)
    {
        if (id <= k && dfn[x[id]] < i) id++;
        int u = map[i];
        D[u] = D[0] - dis(x[id - 1], x[id]) + dis(x[id - 1], u) + dis(u, x[id]) - max[u];
    }
    for (int i = 1; i <= n; i++) printf("%ld\n", D[i]);
    return 0;
}