C++14(g++5.4) 解法, 执行用时: 226ms, 内存消耗: 13260K, 提交时间: 2019-09-14 17:46:09

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<pair<int, int>>> G;

int dfs(int s, int f, int l, int &tot) {
  vector<int> tmp;
  for (auto it: G[s]) if (it.first != f) {
    tmp.push_back(it.second + dfs(it.first, s, l, tot));
  }
  if (tmp.size() == 0) return 0;
  int t = *max_element(tmp.begin(), tmp.end()); 
  if (t < (l + 1)/2) return t;
  //delete it or need -O2

  sort(tmp.begin(), tmp.end());
  multiset<int> S;
  for (auto t: tmp) {
    if (t >= l) tot++;
    else if (S.lower_bound(l-t) != S.end()) tot++, S.erase(S.lower_bound(l-t));
    else S.insert(t);
  }
  return S.empty()?0: *prev(S.end()); 
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> m;
  G.resize(n + 1);
  int s = 0;
  for (int i = 0; i < n - 1; i++) {
    int a, b, l; cin >> a >> b >> l;
    G[a].push_back({b, l});
    G[b].push_back({a, l});
    s += l;
  }
  int lo = 0, hi = s / m + 1;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    int tot = 0;
    dfs(1, -1, mid, tot);
    if (tot < m) hi = mid;
    else lo = mid + 1;
  }
  cout << hi - 1 << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 504ms, 内存消耗: 7188K, 提交时间: 2020-08-15 21:49:59

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,K,ans;
int hd[N],nxt[N],to[N],w[N],tot;
void add(int a,int b,int c)
{
	to[++tot]=b,w[tot]=c,nxt[tot]=hd[a],hd[a]=tot;
}
int dfs(int u,int f)
{
	multiset<int> st;
	for(int i=hd[u];i;i=nxt[i])
	{
		if(to[i]!=f) st.insert(dfs(to[i],u)+w[i]);
	}
	multiset<int>::iterator p1,p2;
	while((p1=st.end())!=st.begin()&&*--p1>=K)
	{
		++ans;
		st.erase(p1);
	}
	int re=0;
	while((p1=st.begin())!=st.end())
	{
		int tmp=*p1;
		st.erase(p1);
		if((p2=st.lower_bound(K-tmp))!=st.end())
		{
			++ans;
			st.erase(p2);
		}
		else re=tmp;
	}
	return re;
}
bool check()
{
	ans=0;
	dfs(1,0);
	return ans>=m;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<n;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	int L=0,R=5e8;
	while(L<R)
	{
		K=L+R+1>>1;
		if(check()) L=K;
		else R=K-1;
	}
	printf("%d\n",L);
}