题解：P8137 [ICPC 2020 WF] ’S No Problem

· · 题解

\gdef \dp{\mathrm{dp}} \gdef \son{\mathrm{son}}

首先你先考虑假设只有一台扫雪机，这个答案最大是 2 \times \sum d。因为你可以对于树的每个边都一进一出一次，把路径搞成一个大环。

然后考虑去除掉这个大环中的两段路径，这样这个环就会断成两条路径，于是就可以把这两条路径当作两个扫雪机的路线了。

于是我们希望知道这两条路径是啥，你想一下就会发现去除的一定是树中的两条不相交的路径，否则如果相交的话就会有的边没有被清扫。由于要求和最小，我们自然希望去除的长度最大，也就是我们要找出树中最长的两条不相交的路径。

这个东西比较典，直接 dp。设：

之所以这么设，是因为若当前节点所有子树的四个结果都被计算出来，就可以利用子树的四个结果计算当前节点的四个结果。

具体地，依次对于每个 v \in \son _ u，我们有：

看着很长，实际上很好理解。最后答案就是 2 \times \sum d - \dp _ {1, 3}，时间复杂度 O(n)。

#include<iostream>
#include<algorithm>
#include<vector>

constexpr int N = 1e5 + 5;

int n, sum_d = 0, dp[N][4];
std::vector<std::pair<int, int> > G[N];

void solve_dp(int u, int father) {
    for(const auto& [v, d] : G[u]) {
        if(v == father) continue; else solve_dp(v, u);
        dp[u][3] = std::max({dp[u][3], dp[u][2] + dp[v][0] + d, dp[u][1] + dp[v][1], dp[u][0] + dp[v][2] + d, dp[v][3]});
        dp[u][2] = std::max({dp[u][2], dp[u][1] + dp[v][0] + d, dp[u][0] + dp[v][1], dp[v][2] + d});
        dp[u][1] = std::max({dp[u][1], dp[u][0] + dp[v][0] + d, dp[v][1]});
        dp[u][0] = std::max({dp[u][0], dp[v][0] + d});
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0), std::cout.tie(0);

    std::cin >> n;
    for(int i = 1; i <= n - 1; ++i) {
        int u, v, d; std::cin >> u >> v >> d; sum_d += d;
        G[u].emplace_back(v, d), G[v].emplace_back(u, d);
    }

    solve_dp(1, 0);
    std::cout << (sum_d << 1) - dp[1][3] << "\n";

    return 0;
}