自动搬运

查看原文

来自洛谷，原作者为

	chroneZ **

搬运于2025-08-24 22:27:56，当前版本为作者最后更新于2023-08-02 16:35:41，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简单手玩一下，可以发现一定存在一种最优方案，能够一棵子树一棵子树地访问掉所有叶结点。

考虑树形 $\text{dp}$。记 $f_u$ 表示当前所在位置为 $u$，且存档点也位于 $u$ 时，走完 $u$ 子树内所有叶结点的最小代价。

设 $u$ 的一个子结点为 $v$，转移可以分为两种，一种是将存档点下放给 $v$，贡献为 $f_v + w_{u, v} + dep_{u}$，其中 $dep_u$ 表示从根结点 $1$ 到点 $u$ 的距离。加 $dep_u$ 是因为我们需要在访问完 $v$ 内所有叶结点后，回到 $u$ 结点以进行下一棵子树的决策。

另一种是不下放存档点，那么就需要从点 $u$ 向 $v$ 子树内的所有的叶结点走一遍。记 $s_u$ 表示 $u$ 子树内叶结点的数量，$g_u$ 表示从点 $u$ 出发到 $u$ 子树内的所有叶结点的，共 $s_u$ 条链的权值和。$g$ 的转移显然，$g_u = \sum \limits_{v \in son_u} g_v + w_{u, v}s_v$。综上，这种转移的贡献为 $g_v + w_{u, v}s_v$。

当然，还可以任选一棵子树作为最后一个被处理的子树，使得处理完它后不需要再回到结点 $u$。这样转移的贡献为 $f_v + w_{u, v}$，且只能对至多一棵子树这样转移。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int N = 1e6 + 10;
struct Graph {
	int head[N], total, v[N << 1], w[N << 1], suf[N << 1];
	Graph() {memset(head, -1, sizeof head);}
	inline void addedge(int x, int y, int t) {
		suf[total] = head[x]; head[x] = total;
		v[total] = y, w[total] = t; total++;
	}
} G;

i64 f[N], g[N], s[N], dep[N];
void dfs(int u, int fa) {
	int child = 0;
	for(int i = G.head[u]; ~i; i = G.suf[i]) {
		int v = G.v[i], w = G.w[i];
		if(v == fa) continue;
		dep[v] = dep[u] + w; dfs(v, u); 
		child++; s[u] += s[v]; g[u] += g[v] + w * s[v];
	}
	if(child == 0) s[u] = 1;
	i64 del = 0;
	for(int i = G.head[u]; ~i; i = G.suf[i]) {
		int v = G.v[i], w = G.w[i];
		if(v == fa) continue;
		i64 cur = min(f[v] + w + dep[u], g[v] + w * s[v]);
		i64 it = f[v] + w;
		del = max(del, cur - it);
		f[u] += cur;
	}
	f[u] -= del;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int n; cin >> n;
	for(int i = 1; i <= n; i++) {
		int k; cin >> k;
		while(k--) {
			int v, w; cin >> v >> w;
			G.addedge(i, v, w), G.addedge(v, i, w);
		}
	}
	dfs(1, -1);
	cout << f[1] << "\n";
}