Submission #1061183

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

struct Info {
	Info() : dist(0), cnt(0){}
	int dist, cnt;
};

struct Node {
	Node(int src, int dst, int l) : src(src), dst(dst), l(l){}
	int src, dst, l;
};

Info dfs(const vector<vector<Node>>& g, int pos, int prev, int d){
	Info res;
	int near = 0, far = 1000000010;
	for(const Node& n : g[pos]){
		if(n.dst == prev) continue;
		Info ni = dfs(g, n.dst, pos, d);
		res.cnt += ni.cnt;
		int nd = ni.dist + n.l;
		if(2 * nd < d){
			near = max(near, nd);
			--res.cnt;
		} else {
			far = min(far, nd);
		}
	}
	if(near + far < d){
		res.dist = far;
	} else {
		res.dist = near;
		++res.cnt;
	}
	return res;
}

int main(){
	int N, K;
	while(cin >> N >> K){
		vector<vector<Node>> g(N);
		for(int i=0;i<N-1;++i){
			int a, b, c; cin >> a >> b >> c;
			--a; --b;
			g[a].push_back(Node(a, b, c));
			g[b].push_back(Node(b, a, c));
		}
		int l = 0, r = 1000000010;
		while(r-l > 1){
			int m = (l+r)/2;
			if(dfs(g, 0, -1, m).cnt >= K){
				l = m;
			} else {
				r = m;
			}
		}
		cout << l << endl;
	}
}

Submission Info

Judge Result