JOI2010春合宿Day2 地域 (Regions)

問題

http://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day2_21.pdf

解法

二分探索でを決めてしまうと、O(N)で、そので個の地域分けが達成できるか判定できそうな気がします。
そこで判定方法を考えます。

とりあえず根付き木をイメージします。
当然ですが、全ての地域は部分木です。
そこで子ノードたちを根とした部分木からその親ノードを根とした部分木の最適な地域の分け方を求めることを考えます。

親のところで子たちの部分木を併合したときの直径についてですが、新たに生まれる経路は親を通る経路だけなので、親から一番遠い2つの(部分木の)葉までの距離の総和だけが新しい直径となる可能性を持ちます。

さて、葉の方から地域分けしてきて、今子ノードたちはそれぞれ別の地域1つに属しています。
親も同様1つの地域にしか属せないので、子ノードたちを根とした各部分木の中のうち直径が最小のものに属すのが最適と分かります。(一番多くのノードを繋げて地域数を減らしてくれそう)
ただし、どの部分木も直径がいっぱいいっぱい(親に辺を伸ばすだけで限界が来ちゃう)ときは親自身が新しい地域を作らなければいけません。

あり得る直径の最大値(3*10^6以下)をLとすると、です。

コード

using namespace std;
 
#define int long long
 
const int INF = LLONG_MAX/893;
 
struct Edge
{
	int to, c;
	Edge() {}
	Edge(int _to, int _c)
	{
		to = _to; c = _c;
	}
 
	bool operator < (const Edge &a) const
	{
		return c < a.c;
	}
};
 
int N, M;
vector<Edge> edge[30000];
 
//(直径, 地域数)
pair<int, int> DFS(int v, int p, int length)
{
	int mi = INF;
	vector<pair<int, int> > ret;
	int sum = 0;
	for (int i = 0; i < edge[v].size(); i++)
	{
		if (edge[v][i].to == p) continue;
		ret.push_back(DFS(edge[v][i].to, v, length));
		sum += ret.back().second;
		if (ret.back().first + edge[v][i].c > length) ret.pop_back();
		else ret.back().first += edge[v][i].c;
	}
	if (ret.size() == 0) return make_pair(0, sum + 1);
	sort(ret.begin(), ret.end());
	int ma = ret[0].first;
	for (int i = 1; i < ret.size(); i++)
	{
		if (ma + ret[i].first <= length)
		{
			ma = max(ma, ret[i].first);
			sum--;
		}
	}
	return make_pair(ma, sum);
}
 
signed main()
{
	cin >> N >> M;
	for (int i = 0; i < N - 1; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		edge[a].push_back(Edge(b, c));
		edge[b].push_back(Edge(a, c));
	}
 
	int l = 0, r = INF;
	while (r - l > 1)
	{
		int mid = (l + r)/2;
		if (DFS(0, -1, mid).second <= M) r = mid;
		else l = mid;
	}
	printf("%lld\n", r);
	return 0;
}