关于频繁使用 vector 带来的效率问题的解决方法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const double eps=1e-4;
int n,L,R;
vector<pair<int,double>> e[N];
int del[N],sz[N],rt,tot;
vector<double> rec,s;
double ans;
void cl(){
	ans=-1e18;
	memset(del,0,sizeof(del));
}
void temp_cl(){
	rec.clear();
	s.clear();
}
vector<double> rep1(vector<double> f){
	vector<double> res(f.size(),-1e18);
	deque<pair<double,int>> q;
	int len=R-L+1;
	for(int i=1;i<(int)f.size();i++){
		while(!q.empty()&&q.back().first<=f[i]) q.pop_back();
		while(!q.empty()&&q.front().second<i-len+1) q.pop_front();
		q.push_back({f[i],i});
		res[i]=q.front().first;
	}
	return res;
}
vector<double> rep2(vector<double> f){
	vector<double> res(f.size(),-1e18);
	deque<pair<double,int>> q;
	int len=R-L+1;
	for(int i=(int)f.size()-1;i>=1;i--){
		while(!q.empty()&&q.back().first<=f[i]) q.pop_back();
		while(!q.empty()&&q.front().second>i+len-1) q.pop_front();
		q.push_back({f[i],i});
		res[i]=q.front().first;
	}
	return res;
}
vector<double> mer(vector<double> a,vector<double> b){
	if(a.size()<b.size()) swap(a,b);
	vector<double> res=a;
	for(int i=0;i<(int)b.size();i++){
		res[i]=max(res[i],b[i]);
	}
	return res;
}
void dfs0(int u,int fa){
	sz[u]=1;
	for(auto [v,w]:e[u]){
		if(v==fa||del[v]) continue;
		dfs0(v,u);
		sz[u]+=sz[v];
	}
}
void dfs1(int u,int fa){
	for(auto [v,w]:e[u]){
		if(v==fa||del[v]) continue;
		if(sz[v]>tot/2){
			dfs1(v,u);
			return;
		}
	}
	rt=u;
}
void dfs2(int u,int fa,double dis,int len){
	s[len]=max(s[len],dis);
	if(L<=len&&len<=R) ans=max(ans,dis);
	for(auto [v,w]:e[u]){
		if(v==fa||del[v]) continue;
		dfs2(v,u,dis+w,len+1);
	}
}
void tree_div(int u){
	dfs0(u,0);
	tot=sz[u];
	dfs1(u,0);
	int r=rt;
	del[r]=1;
	sort(e[r].begin(),e[r].end(),[&](pair<int,double> &t1,pair<int,double> &t2){
		return sz[t1.first]<sz[t2.first];
	});
	for(auto [v,w]:e[r]){
		if(del[v]) continue;
		s.assign(sz[v]+1,-1e18);
		dfs2(v,r,w,1);
		if(!rec.empty()){
			auto w1=rep1(rec);
			auto w2=rep2(rec);
			for(int i=1;i<=sz[v];i++){
				int ml=L-i,mr=R-i;
				if(1<=mr&&mr<(int)rec.size()){
					ans=max(ans,w1[mr]+s[i]);
				}
				else if(mr>=(int)rec.size()&&ml<(int)rec.size()){
					ans=max(ans,w2[max(ml,1)]+s[i]);
				}
			}
		}
		rec=mer(rec,s);
	}
	temp_cl();
	for(auto [v,w]:e[r]){
		if(del[v]) continue;
		tree_div(v);
	}
}
signed main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>L>>R;
	for(int i=1;i<n;i++){
		int x,y;
		double w;
		cin>>x>>y>>w;
		e[x].push_back({y,w});
		e[y].push_back({x,w});
	}
	double le=0,ri=1e6+5,mid;
	while(le+eps<ri){
		mid=(le+ri)/2;
		for(int i=1;i<=n;i++){
			for(auto& [v,w]:e[i]){
				w-=mid;
			}
		}
		cl();
		tree_div(1);
		for(int i=1;i<=n;i++){
			for(auto& [v,w]:e[i]){
				w+=mid;
			}
		}
		if(ans>0) le=mid;
		else ri=mid;
	}
	cout<<fixed<<setprecision(3)<<le<<"\n";
}