【题解】LuoGu5021：赛道修建

原题传送门
二分答案
树形dp验证
对于每个点的儿子中尽可能两两组合（贪心）达到最大值，最好在这个基础之下还能选择一个尽可能长度大的路径和自己组合起来上传到父亲上去

把儿子的值存下来，排序，首先用贪心（头尾指针扫描）求出最大赛道值，接着发现上传的值的大小满足可二分性，就二分，看看去掉二分的mid剩下的还能不能两两组合达到之前的答案

Code：

#include <bits/stdc++.h>
#define maxn 50010
using namespace std;
struct Edge{
	int to, next, len;
}edge[maxn << 1];
int num, head[maxn], tot, a[maxn], dp[maxn], n, m, cnt;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int z){ edge[++num] = (Edge){y, head[x], z}, head[x] = num; }

void dfs(int u, int pre, int mid){
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs(v, u, mid);
	}
	tot = 0;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) a[++tot] = dp[v] + edge[i].len;
	}
	sort(a + 1, a + 1 + tot);
	while (tot && a[tot] >= mid) --tot, ++cnt;
	int j = 1, sum = 0;
	for (int i = tot; i; --i){
		while (j < i && a[i] + a[j] < mid) ++j;
		if (j >= i) break;
		++cnt, ++sum, ++j;
	}
	int l = 1, r = tot, ans = 0;
	while (l <= r){
		int Mid = (l + r) >> 1, s = 0;
		j = 1;
		for (int i = tot; i; --i){
			if (i == Mid) continue;
			while (j < i && a[i] + a[j] < mid || j == Mid) ++j;
			if (j >= i) break;
			++s, ++j;
		}
		if (s >= sum) ans = Mid, l = Mid + 1; else r = Mid - 1;
	}
	dp[u] = a[ans];
}

bool check(int mid){
	cnt = 0;
	dfs(1, 0, mid);
	return cnt >= m;
}

int main(){
	n = read(), m = read();
	int l = 0, r = 0, ans = 0;
	for (int i = 1; i < n; ++i){
		int x = read(), y = read(), z = read();
		addedge(x, y, z), addedge(y, x, z);
		r += z;
	}
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(mid)) ans = mid, l = mid+ 1; else r = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}