求助TLE 0pts
查看原帖
求助TLE 0pts
1313003
hwc2011楼主2025/7/23 20:34
#include<bits/stdc++.h> 
using namespace std;
const int N=100005,inc=-1e9;
int n,L,R,st[N],siz[N],f[N],vis[N],root,rt,sum,mxt,mxv,flg;
double l,r,mid,tmp[N],t[N],ans;
struct node{
	int v,w;
};
vector<node>e[N],E[N];
void get_root(int u,int fa){
	siz[u]=1;
	f[u]=0;
	for(auto i:e[u]){
		int v=i.v;
		if(v==fa||vis[v]) continue;
		get_root(v,u);
		f[u]=max(f[u],siz[v]);
		siz[u]+=siz[v]; 
	}
	f[u]=max(f[u],sum-siz[u]);
	if(f[u]<f[root]) root=u;
}
void get_dis(int u,int dep,double dis,int fa){
	mxv=max(mxv,dep);
	tmp[dep]=max(tmp[dep],dis);
	for(auto i:e[u]){
		int v=i.v,w=i.w;
		if(v==fa||vis[v]) continue;
		get_dis(v,dep+1,dis+w-mid,u);
	}
}
void calc(int u){
	for(auto i:e[u]){
		int v=i.v,w=i.w;
		if(vis[v]) continue;
		get_dis(v,1,w-mid,0);
		int bot=1,top=0;
		for(int ld=mxt,rd=1;rd<=mxv;rd++){
			while(bot<=top&&st[bot]>R-rd) bot++;
			while(ld>=L-rd&&ld>=0){
				while(bot<=top&&t[st[top]]<=t[ld]) r--;
				st[++top]=ld--;
			}
			if(bot<=top&&t[st[bot]]+tmp[rd]>0){
				flg=1;
				break;
			}
		}
		for(int j=1;j<=mxv;j++) t[j]=max(t[j],tmp[j]);
		mxt=max(mxt,mxv);
		for(int j=1;j<=mxv;j++) tmp[j]=inc;
		mxv=0;
		if(flg) break;
	}
	for(int i=1;i<=mxt;i++) t[i]=inc;
	mxt=0;
}
void dfs(int u){
	vis[u]=1;
	calc(u);
	if(flg){
		vis[u]=0;
		return;
	}
	for(auto i:e[u]){
		int v=i.v,w=i.w;
		if(vis[v]) continue;
		if(flg) break;
	}
	vis[u]=0;
}
void build(int u){
	vis[u]=1;
	for(auto i:E[u]){
		int v=i.v,w=i.w;
		if(vis[v]) continue;
		root=0;
		sum=siz[v];
		get_root(v,u);
		e[u].push_back({root,w});
		build(root);
	}
	vis[u]=0;
}
bool check(){
	flg=0;
	dfs(rt);
	return flg;
}
signed main(){
	scanf("%d%d%d",&n,&L,&R);
	for(int i=1;i<=n;i++) t[i]=tmp[i]=inc;
	for(int i=1,u,v,w;i<n;i++){
		scanf("%d%d%d",&u,&v,&w);
		l=min(l,1.0*w);
		r=max(r,1.0*w);
		E[u].push_back({v,w});
		E[v].push_back({u,w});
	}
	f[root=0]=1e9;
	sum=n;
	get_root(1,0);
	rt=root;
	build(root);
	while(l<=r-1e-5){
		mid=(l+r)/2;
		if(check()) l=ans=mid;
		else r=mid;
	}
	printf("%.3lf",ans);
}
2025/7/23 20:34
加载中...