自动搬运

查看原文

来自洛谷，原作者为

	TemplateClass **

搬运于2025-08-24 22:36:17，当前版本为作者最后更新于2025-03-28 20:48:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

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

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

• $\dp _ {i, 0}$ 表示根为 $i$ 的子树中从根出发最长的一条路径的长度；
• $\dp _ {i, 1}$ 表示根为 $i$ 的子树中最长的一条路径的长度；
• $\dp _ {i, 2}$ 表示表示根为 $i$ 的子树中最长的两条路径（其中一条从根出发）的长度和；
• $\dp _ {i, 3}$ 表示表示根为 $i$ 的子树中最长的两条路径的长度和。

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

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

• $\dp _ {u, 3} \gets \max \!\left\{ \dp _ {u, 3}, \dp _ {u, 2} + \dp _ {v, 0} + d _ {uv}, \dp _ {u, 1} + \dp _ {v, 1}, \dp _ {u, 0} + \dp _ {v, 2} + d _ {uv}, \dp _ {v, 3} \right\}$；
• $\dp _ {u, 2} \gets \max \!\left\{ \dp _ {u, 2}, \dp _ {u, 1} + \dp _ {v, 0} + d _ {uv}, \dp _ {u, 0} + \dp _ {v, 1}, \dp _ {v, 2} + d _ {uv} \right\}$；
• $\dp _ {u, 1} \gets \max \!\left\{ \dp _ {u, 1}, \dp _ {u, 0} + \dp _ {v, 0} + d _ {uv}, \dp _ {v, 1} \right\}$；
• $\dp _ {u, 0} \gets \max \!\left\{ \dp _ {u, 0}, \dp _ {v, 0} + d _ {uv} \right\}$。

看着很长，实际上很好理解。最后答案就是 $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;
}