P5021 赛道修建

题面:https://www.luogu.org/problem/P5021
本题首先看到最小值最大就可以想到二分,即二分一个mid作为答案,设f[u]为以u为根的子树中,不选作赛道的边最大为多少,因为赛道的选定只有两种情况,一是继续连向根的父亲,二是从儿子到根再到儿子,那么f[v]+w>=mid时即找到了一条赛道,那么直接计入答案,剩下的路径则判断是否可以两两搭配组成一条赛道,若找不到可匹配的赛道,那么选其中最大值计入f[u]向上传递,因为它最有可能和根的父亲组成一条赛道.最后每次判断找到的路径条数是否>=m即可.
Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<set>
using namespace std;
const int N=50005;
int cnt,head[N],n,m,tot,f[N],ans,mid;
int read(){
    int x=0,f=1;
	char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct Node{
	int u,v,w,nxt;
}edge[N*2];
inline void add(int u,int v,int w){
	++cnt;
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
inline void dfs(int u,int fa){
	multiset<int> Q;
	for(register int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].v,w=edge[i].w;
		if(v!=fa){
			dfs(v,u);
			if(f[v]+w>=mid){
				++tot;
			}
			else{
				Q.insert(f[v]+w);
			}
		}
	}
	while(!Q.empty()){
		multiset<int> ::iterator it=Q.begin();
		Q.erase(it);
		multiset<int> ::iterator pos=Q.lower_bound(mid-*it);
		if(pos==Q.end()){
			f[u]=max(f[u],*it);
		}
		else{
			++tot;
			Q.erase(pos);
		}
	}
}
inline bool check(){
	for(register int i=1;i<=n;i++){
		f[i]=0;
	}
	tot=0;
	dfs(1,0);
	if(tot>=m){
		return 1;
	}
	return 0;
}
signed main(){
	n=read(),m=read();
	for(register int i=1;i<n;i++){
		int a,b,l;
		a=read(),b=read(),l=read();
		add(a,b,l);
		add(b,a,l);
	}
	int l=1,r=500000000;
	while(l<=r){
		mid=(l+r)/2;
		if(check()){
			ans=mid;
			l=mid+1;
		}
		else{
			r=mid-1;
		}
	}
	printf("%d\n",ans);
    return 0;
}
P5021 赛道修建

推荐阅读
