题解 [NOIP2018 提高组] 赛道修建

题目链接

挺综合的一道题目。

询问最小值最大，考虑二分最小值，二分上下界是 \([最小边权,树的直径]\)，但是为了方便我们直接设为 \([1,5\times 10^8]\) 即可。

考虑如何 \(check\)，可以采用类似树形 \(dp\) 的方式进行贪心。对于节点 \(u\) 的子树，\(u\) 内部的点显然可以构成几条链，同时我们也可以从 \(u\) 内部引一条链出去，和上面的节点进行搭配，从而使得边权和大于我们二分的值。

问题也就转化为：将 \(u\) 的儿子尽可能的凑合，凑合出最多的链数量，然后从没有凑合好的链中选出一条最长的传上去，也就是说：在保证节点 \(u\) 内部的链数量最多，使得上传的权值最大。

对于节点 \(u\) 的儿子传上来的权值 \(val\)，若 \(val\ge mid\)，则直接计入贡献即可；反之先放到一边。

对于刚才不符合条件的 \(val\)，进行处理：由于要保证最终剩下来的最大，且一对搭配的贡献始终是 \(1\)，所以我们从小开始，查找与之搭配符合条件的，并选上，最终剩下的就是最大的。返回到父亲节点即可。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=5e4+10;
int n,m;
struct node {
	int to,w;
};
vector<node> g[N];

void add(int x,int y,int z) {
	g[x].push_back({y,z});
}

int sum=0;

LL dfs(int nd,int fa,LL s) {
	multiset<LL> st,st2;
	multiset<LL>::iterator it;
	for(node t:g[nd]) {
		int x=t.to,w=t.w;
		if(x==fa) continue;
		LL res=dfs(x,nd,s)+(LL)w;
		if(res>=s) sum++;
		else st.insert(res);
	}
	LL maxn=0;
	while(st.size()>=2) {
		LL minn=*st.begin(); st.erase(st.begin());
		it=st.lower_bound(s-minn);
		if(it==st.end()) { maxn=max(maxn,minn); continue; }
		sum++;
		st.erase(it);
	}
	if(st.size()) return max(maxn,*(--st.end()));
	else return maxn;
}

int check(LL s) {
	sum=0;
	dfs(1,0,s);
	if(sum>=m) return 1;
	else return 0;
}

int main() {
	cin>>n>>m;
	for(int i=1;i<n;i++) {
		int a,b,l; cin>>a>>b>>l;
		add(a,b,l); add(b,a,l);
	}
	LL l=1,r=500000000;
	while(l<r) {
		LL mid=(l+r+(LL)1)/2;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}