点击查看题解视频

（不知道为什么很多人把这题划分为树形 DP，我觉得是贪心）

Subtask 1：$m=1$

对于 $m=1$ 的情况，直接求树的直径即可。

时间复杂度 $O(n)$，期望得分 $\rm{20\ pts}$。

Subtask 2：$a_i=1$

菊花图的情况，按边权从大到小排序。

答案为 $\min\limits_{i=1}^m \{l_i+l_{2m-i+1}\}$。

时间复杂度 $O(n\log n)$，期望得分 $\rm{15\ pts}$

Subtask 3：$b_i=a_i+1$

一条链的情况，显然二分答案，贪心判断即可。

时间复杂度 $O(n\log n)$，期望得分 $\rm{20\ pts}$。 

Correct Answer

显然这道题的主体是二分答案。

考虑判断当前答案 $k$ 是否满足。

我们要构造 $\ge m$ 条长度 $\ge k$ 的路径，而且还不能有重边。

一开始我在尝试淀粉质，但发现无重边这个东西实在是难以处理。

不如另辟蹊径，我们考虑枚举一个点 $u$ 对答案的贡献。

也就是经过点 $u$，且 $u$ 的深度是路径上所有点中深度的最小值的路径个数。

首先，递归到子树里，并把子树里 $\lt k$ 的最大一条路径长度穿上来，保存在一个 `std::multiset` 中。

然后利用 `std::multiset` 的二分统计答案，在这个过程中统计出 $\lt k$ 的最大路径长度，递归回去。

时间复杂度 $O(n\log^2 n)$。

// Problem: #438. 【NOIP2018】赛道修建
// Contest: UOJ
// URL: https://uoj.ac/problem/438
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define SIT std::multiset<int>::iterator
typedef std::pair<int,int> pii;

const int maxn = 5e4 + 5;
std::vector<pii> G[maxn];
int n,m,dp[maxn],ans,res;

void DFS(int u,int fa) {
	for(auto& [v , w] : G[u]) {
		if(v == fa)continue ;
		DFS(v , u);
		res = std::max(res , dp[u] + dp[v] + w);
		dp[u] = std::max(dp[u] , dp[v] + w);
	}
	return ;
}

void GetMaxLength() {
	res = 0;
	DFS(1 , 0);
	return ;
}

int dfs(int u,int fa,int k) {
	std::multiset<int> s;
	for(auto& [v , w] : G[u]) {
		if(v == fa)continue ;
		int t = dfs(v , u , k) + w;
		if(t >= k)++ ans;
		else s.insert(t);
	}
	
	int Max = 0;
	for(;!s.empty();) {
		res = *s.begin();
		s.erase(s.begin());
		SIT it = s.lower_bound(k - res);
		if(it == s.end())Max = std::max(Max , res);
		else s.erase(it),++ ans;
	}
	
	return Max;
}

int main() {
	scanf("%d %d",&n,&m);
	for(int i = 1,u,v,t;i < n;++ i) {
		scanf("%d %d %d",&u,&v,&t);
		G[u].pb(v , t);
		G[v].pb(u , t);
	}
	
	GetMaxLength();
	int l = 1,r = res,mid;
	while(l <= r) {
		mid = (l + r) >> 1;
		ans = 0;
		dfs(1 , 0 , mid);
		if(ans >= m)l = mid + 1;
		else r = mid - 1;
	}
	
	printf("%d\n",r);
	return 0;
}