自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:03:42，当前版本为作者最后更新于2024-09-16 23:52:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

鲜花：这题 idea 来自我真名的拼音首字母缩写。

首先考虑一个 $O(n^2)$ 的 dp。先枚举 $i$，然后设 $dp_u$ 为 $u$ 子树内的答案。对于 $u$ 的儿子 $v$，若定为重儿子则造成 $dp_v$ 的贡献，否则造成 $dp_v+w_{u,v}$ 的贡献。最优策略就是贪心地将 $dp_v+w_{u,v}$ 的前 $i$ 大设为重儿子，可以得到转移：

$$dp_u=\max((i+1)_{\text{th}}(\{dp_v+w_{u,v}\mid v\in\operatorname{son}(u)\}),\max_{v\in\operatorname{son}(u)}dp_v) $$

其中 $k_{\text{th}}(S)$ 表示集合 $S$ 内的第 $k$ 大。单次可用 nth_element 函数做到 $O(n)$。

可以发现一个事情：当 $i\ge d_u$ 时，我们可以把它的所有儿子都设为重儿子。所以这些 $u$ 本质上是没用的，只要保留所有 $d_u>i$ 的节点后建虚树，节点总数是 $O(\sum^{n-1}_i\sum_u[d_u>i])=O(\sum_ud_u)=O(n)$ 的。

但是转移复杂度还是错的啊？你先别急，我们每个节点开一个平衡树/可删对顶堆，维护其下所有 $dp_v+w_{v,u}$ 的值即可。新建虚树时暴力删除所有删掉的节点，进行 dp 时暴力加上所有有用的节点，修改次数是 $O(n)$ 的。

但是虚树是 10 级算法我不会啊？你先别急，我们可以在 $i=x-1$ 的虚树上面建 $i=x$ 的虚树，每次搜第一遍找出哪些点要用，再搜第二遍连父亲即可，时间复杂度是所有虚树的大小总和，也是 $O(n)$ 的。总复杂度带个 priority_queue 或者 multiset 的 log。

代码异常简单。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 10;

struct heap {
	
	multiset<ll, greater<ll>> s1, s2;
	
	void insert(ll x) {
		if (s2.empty() || x >= *s2.begin()) s1.insert(x);
		else s2.insert(x);
	}
	
	void erase(ll x) {
		if (s1.find(x) != s1.end()) s1.erase(s1.find(x));
		else if (s2.find(x) != s2.end()) s2.erase(s2.find(x));
	}
	
	ll kth(int rk) {
		if (rk > s1.size() + s2.size()) return 0;
		for (; s1.size() < rk; s1.insert(*s2.begin()), s2.erase(s2.begin()));
		for (; s1.size() > rk; s2.insert(*--s1.end()), s1.erase(--s1.end()));
		return s2.empty() ? 0 : *s2.begin();
	}
	
} s[MAXN]; 

struct node {
	int v, w;
	node(int v = 0, int w = 0) : v(v), w(w) {}
}; vector<node> g[MAXN], tg[MAXN];

int k, d[MAXN]; ll dp[MAXN];

void dfs(int u, int f) {
	ll res = 0;
	for (node p : g[u]) {
		if (p.v == f) continue; dfs(p.v, u);
		res = max(res, dp[p.v]), s[u].insert(dp[p.v] + p.w);
	}
	dp[u] = max(res, s[u].kth(k));
}

int vis[MAXN], sz[MAXN];

void init(int u, int f) {
	int cnt = 0; sz[u] = vis[u] = (!f || d[u] > k);
	for (node p : g[u]) {
		if (p.v == f) continue; init(p.v, u);
		if (sz[p.v]) cnt++; sz[u] += sz[p.v];
	}
	if (!vis[u] && cnt > 1) vis[u] = 1, sz[u]++;
}

void build(int u, int f, int t, int w) {
	for (node p : g[u]) if (p.v != f) s[u].erase(dp[p.v] + p.w);
	for (node p : g[u]) if (p.v != f && !sz[p.v]) s[u].insert(p.w);
	if (vis[u]) { if (t) tg[t].emplace_back(u, w); t = u; }
	else for (node &p : g[u]) p.w = w;
	for (node p : g[u]) if (p.v != f && sz[p.v]) build(p.v, u, t, p.w);
	g[u] = tg[u], tg[u].clear();
}

int n;

int main() {
	scanf("%d", &n);
	for (int i = 1, u, v, w; i < n; i++) {
		scanf("%d%d%d", &u, &v, &w);
		g[u].emplace_back(v, w), d[u]++;
		g[v].emplace_back(u, w), d[v]++;
	}
	for (int i = 2; i <= n; i++) d[i]--;
	dfs(1, 0), printf("%lld ", dp[1]);
	for (k = 1; k < n; k++) {
		init(1, 0), build(1, 0, 0, 0), dfs(1, 0);
		printf("%lld ", dp[1]);
	}
}

审核说还存在一个长剖做法，但是我不会长剖，有会的同学可以写一下谢谢喵。

赛时被骂说这题跟 TECHNOPOLIS 2085 太卡常了，一看写的不是直接搜而是 10 级算法，令人忍俊不禁。