nkoj P5975题解

$\texttt{Description}$

给你 $n$ 个节点的树，要你选择 $k$ 个点 $a_1,a_2…a_k$，使得 $\sum\limits_{i=1}^{i<k} dis(a_i,a_{i+1})$ 最小，$dis(u,v)$ 表示节点 $u$ 和 $v$ 的距离。树的边权均为正整数且小于 $10^5$。

$\texttt{Data Range:}1\le k\le n\le 3000$

$\texttt{Solution}$

算是比较毒瘤的一个树形 dp了吧。需要充分挖掘题目性质，否则直接树形背包会非常痛苦并且最后发现做不出来。

首先，我们选出的 $k$ 个点一定是紧密相连的，否则如果中间有空隙，那么用这些空隙位置的点替换原来的点一定更优。

因此选择的 $k$ 个点一定构成一棵树。当选择好了这棵树后，我们需要找到一条最短的遍历整棵树的路径。那么这条最短路径的长度一定是所有边权之和的两倍减去树的直径。因为路径经过了一条边还要回来，但是有些路径是可以不回来的。选择的这些只经过一次的边构成一条链，我们自然希望这条链最长，因此这条链长度即为树的直径。

如果直接进行树形背包，不知道直径是哪条链，也就没法 dp。因此考虑在状态中加入对直径的限制：$dp_{u,i,x}$ 表示在以 $u$ 为根的子树中，选择 $i$ 个点，其中包含了 $x$ 个直径端点（$0\le x\le 2$)，最小代价是多少。

有一个注意的地方，树形背包的填表法时间复杂度是假的，之前没被卡过但在这题上被卡了。只有刷表法复杂度是经过严格证明 $O(n^2)$ 的。

$$dp_{u,i+j,0}=min(dp_{u,i,0}+dp_{v,j,0}+len(u,v)\times 2)$$ $$dp_{u,i+j,1}=min(dp_{u,i,1}+dp_{v,j,0}+len(u,v)\times 2,dp_{u,i,0}+dp_{v,j,1}+len(u,v))$$ $$dp_{u,i+j,2}=min(dp_{u,i,0}+dp_{v,j,2}+len(u,v)\times 2,dp_{u,i,1}+dp_{v,j,1}+len(u,v),dp_{u,i,2}+dp_{v,j,0}+len(u,v)\times 2)$$

$v$ 是 $u$ 的儿子，$len(u,v)$ 表示连接 $u,v$ 两点的边的长度。

$\texttt{Code}$

#include <cstdio>
#include <cstring>

inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, w, nxt;
} e[6005];
int head[3005], dp[3005][3005][3], cnt[3005], tot, n, k, ans = 2e9;
inline void AddEdge(const int u, const int v, const int w) {
	e[++ tot].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;
}
void dfs(const int u, const int fa) {
	dp[u][0][0] = dp[u][1][0] = dp[u][1][1] = 0;
	cnt[u] = 1;
	for (int I(head[u]); I; I = e[I].nxt) if (e[I].to != fa) {
		const int v(e[I].to);
		dfs(v, u);
		for (int i(min(cnt[u], k)); i; -- i)
		for (int j(1); j <= cnt[v] && i + j <= k; ++ j) {
			int t0(dp[u][i][0]), t1(dp[u][i][1]), t2(dp[u][i][2]);
			dp[u][i + j][0] = min(dp[u][i + j][0], t0 + dp[v][j][0] + e[I].w * 2);
			dp[u][i + j][1] = min(dp[u][i + j][1], min(t1 + dp[v][j][0] + e[I].w * 2, t0 + dp[v][j][1] + e[I].w));
			dp[u][i + j][2] = min(dp[u][i + j][2], min(t0 + dp[v][j][2] + e[I].w * 2, min(t1 + dp[v][j][1] + e[I].w, t2 + dp[v][j][0] + e[I].w * 2)));
		}
		ans = min(ans, dp[u][k][2]);
		cnt[u] += cnt[v];
	}
}

int main() {
	memset(dp, 0x3f, sizeof dp);
	scanf("%d%d", &n, &k);
	if (k == 1) return puts("0"), 0;
	for (int i(1); i < n; ++ i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		AddEdge(u, v, w), AddEdge(v, u, w);
	}
	dfs(1, -1);
	printf("%d", ans);
	return 0;
}