[NOIp2018提高组]赛道修建

[NOIp2018提高组]赛道修建

题目大意：

给你一棵(n(nle5 imes10^4))个结点的树，从中找出(m)个没有公共边的路径，使得第(m)长的路径最长。问第(m)长的路径最长可以是多少。

思路：

二分答案+树形DP。(f[x])表示以(x)为根的子树中最多能找出几个长度(ge k)的路径。(g[x])表示去掉已经满足的路径，从(x)子树内往上连的最长的路径有多长。

转移时将所有子结点的贡献(g[y]+w)排序。若贡献已经(ge k)，那么就直接计入答案。否则从小到大枚举每一个贡献，找到能与其配对的最小的贡献，计入答案。如果找不到能与之配对的贡献，那么就用它来更新(g[x])。可以证明这样能够在保证(f[x])最大化的情况下，最大化(g[x])。

时间复杂度(mathcal O(nlog nlog)值域())。

源代码：

#include<set>
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<algorithm>
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
const int N=5e4+1;
struct Edge {
	int to,w;
};
std::vector<Edge> e[N];
inline void add_edge(const int &u,const int &v,const int &w) {
	e[u].push_back((Edge){v,w});
	e[v].push_back((Edge){u,w});
}
std::multiset<int> t;
int f[N],g[N],len;
void dfs(const int &x,const int &par) {
	f[x]=0;
	for(auto &j:e[x]) {
		const int &y=j.to;
		if(y==par) continue;
		dfs(y,x);
		f[x]+=f[y];
	}
	for(auto &j:e[x]) {
		const int &y=j.to;
		if(y==par) continue;
		t.insert(g[y]+j.w);
	}
	while(!t.empty()) {
		const int u=*t.rbegin();
		if(u>=len) {
			f[x]++;
			t.erase(t.find(u));
		} else {
			break;
		}
	}
	g[x]=0;
	while(!t.empty()) {
		const int u=*t.begin();
		t.erase(t.begin());
		auto p=t.lower_bound(len-u);
		if(p==t.end()) {
			g[x]=u;
		} else {
			t.erase(p);
			f[x]++;
		}
	}
	t.clear();
}
inline int calc(const int &k) {
	len=k;
	dfs(1,0);
	return f[1];
}
int main() {
	const int n=getint(),m=getint();
	int l=INT_MAX,r=0;
	for(register int i=1;i<n;i++) {
		const int u=getint(),v=getint(),w=getint();
		add_edge(u,v,w);
		l=std::min(l,w);
		r+=w;
	}
	while(l<=r) {
		const int mid=(l+r)>>1;
		if(calc(mid)>=m) {
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	printf("%d
",l-1);
	return 0;
}