欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[NOIP2018]track——二分答案+树上贪心

程序员文章站 2022-05-08 17:56:33
...

联赛之后首次发博客…

题目大意:

给定一颗含有n个节点的树,求找出m条树上路径,使得这m条树上路径的长度的最小值最大。

思路:

大家都说这题好水,但是我联赛的时候还是没有想出来,最后暴力都打挂了。
首先看到最小值最大,这很明显是在提示我们二分答案,我们二分一个最小值limlim之后在树上尽量找更多的路径长度lim\geq lim,然后判断这样的路径条数是否大于m。
考虑二分之后如何judge,很容易望树形dp的思路上面去想,设dpudp_u表示u这颗子树内最多选多少条大于lim的路径,然后考虑从子树转移过来。
假设我们目前要在u的子树v中选出一条路径,那么可以发现,如果选出了这条路径之后dpvdp_v的贡献还减少了,那么还不如不选,因为新添加的路径至多贡献1。
于是我们从子树转移过来时便没有必要考虑dpvdp_v的变化,我们只需要求出在满足dpvdp_v最大的情况下求出从v的子树内可以延伸出的最长路径的长度lenvlen_v,对于u的每个儿子v,将lenv+wu,vlen_v+w_{u,v}单独取出来,然后在其中找到最多的配对数量即可。同时为了保证在dpudp_u最大的情况下求出最大的lenulen_u,我们把这些路径放入一个multiset中,从小到大贪心选取,最后没有选取的里面取max作为lenulen_u即可。

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define MREP(i,x) for(int i=beg[x],v;v=to[i],i;i=las[i])
#define debug(x) cout<<#x<<"="<<x<<endl
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
typedef long long ll;

using namespace std;

void File(){
	freopen("luogu5021.in","r",stdin);
	freopen("luogu5021.out","w",stdout);
}

template<typename T>void read(T &_){
	T __=0,mul=1; char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')mul=-1;
		ch=getchar();
	}
	while(isdigit(ch))__=(__<<1)+(__<<3)+(ch^'0'),ch=getchar();
	_=__*mul;
}

const int maxn=5e4+10;
int n,m;
int beg[maxn],las[maxn<<1],to[maxn<<1],cnte=1;
int dp[maxn];
ll w[maxn<<1],len[maxn],sum;
multiset<ll>st;
multiset<ll>::iterator it;

void add(int u,int v,ll tw){
	las[++cnte]=beg[u]; beg[u]=cnte; to[cnte]=v; w[cnte]=tw;
	las[++cnte]=beg[v]; beg[v]=cnte; to[cnte]=u; w[cnte]=tw;
}

void init(){
	read(n); read(m);
	int u,v; ll tw;
	REP(i,1,n-1)read(u),read(v),read(tw),add(u,v,tw);
}

namespace get_width{
	ll dep[maxn];
	int who[maxn];
	void dfs(int u,int f){
		dep[u]=0; who[u]=u;
		MREP(i,u)if(v!=f){
			dfs(v,u);
			if(dep[v]+w[i]>dep[u]){
				dep[u]=dep[v]+w[i];
				who[u]=who[v];
			}
		}
	}
	void work(){
		dfs(1,0);
		int ss=who[1];
		dfs(ss,0);
		sum=dep[ss];
	}
}

void dfs(int u,int f,ll lim){
	MREP(i,u)if(v!=f){
		dfs(v,u,lim);
		dp[u]+=dp[v];
	}
	st.clear();
	MREP(i,u)if(v!=f){
		st.insert(len[v]+w[i]);
		st.insert(0);
	}
	while(st.size()>=2){
		ll tmp=*st.begin();
		st.erase(st.begin());
		it=st.lower_bound(lim-tmp);
		if(it==st.end())len[u]=max(len[u],tmp);
		else ++dp[u],st.erase(it);
	}
	if(!st.empty())len[u]=max(len[u],*st.begin());
}

bool judge(ll x){
	memset(dp,0,sizeof(dp));
	memset(len,0,sizeof(len));
	dfs(1,0,x);
	return dp[1]>=m;
}

void work(){
	get_width::work();
	ll l=1,r=sum;
	while(l<r){
		ll mid=(l+r+1)>>1;
		if(judge(mid))l=mid;
		else r=mid-1;
	}
	printf("%lld\n",l);
}

int main(){
	File();
	init();
	work();
	return 0;
}