一棵大小为 \(n\) 的树，边带权。选 \(m\) 条链使得长度和最小的链最大。
\(m<n\leq5\times10^4\)
贪心，二分答案
最小最大？二分
先看部分分
-
菊花图
二分答案，顺序贪心匹配。
-
二叉树
每个节点两种情况，选一个儿子往上算贡献，两个儿子合成一条链。
于是可以将两种做法结合
对于每个节点，往上算贡献、贪心匹配两个儿子
至于实现，可以考虑 \(multiset\) ，也可以排序+二分
时间复杂度 \(O(n\log^2n)\) ，空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, m, mid, h[maxn];
multiset <int> s;
struct edges {
int nxt, to, w;
edges(int x = 0, int y = 0, int z = 0) :
nxt(x), to(y), w(z) {}
} e[maxn << 1];
void addline(int u, int v, int w) {
static int cnt;
e[++cnt] = edges(h[u], v, w), h[u] = cnt;
e[++cnt] = edges(h[v], u, w), h[v] = cnt;
}
int dfs(int u, int f, int& l) {
int res = 0;
for (int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (v != f) {
int tmp;
res += dfs(v, u, tmp);
if ((tmp += e[i].w) < mid) {
s.insert(tmp);
} else {
res++;
}
}
}
l = 0;
while (!s.empty()) {
int tmp = *s.begin();
s.erase(s.begin());
auto it = s.lower_bound(mid - tmp);
if (it != s.end()) {
s.erase(it), res++;
} else {
l = max(l, tmp);
}
}
return res;
}
int main() {
int sum = 0;
scanf("%d %d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
addline(u, v, w), sum += w;
}
int l = 1, r = sum, res, tmp;
while (l <= r) {
mid = (l + r) >> 1;
dfs(1, 0, tmp) < m ? r = mid - 1 : l = (res = mid) + 1;
}
printf("%d", res);
return 0;
}