rt

加强版的代码交上去只有68分，求调QwQ

代码如下:

#include <bits/stdc++.h>
#define maxn 300005
#define INF (1ll<<60)
#define my_rand(a,b) rand()%(b-a)+a
#define debug(x) cout<<"debug "<<x<<endl;
#define For( i , j , k ) for( ll i = ( j ) ; i <= ( k ) ; ++ i )
#define For__( i , j , k ) for( ll i = ( j ) ; i >= ( k ) ; -- i )
using namespace std;
typedef long long ll;
inline int read() {
	ll num=0,f=1;
	char c=' ';
	while(c<'0'||c>'9') {
		c=getchar();
		if(c=='-') f=-1;
	}
	while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
	return num*f;
}
ll n,s;
struct Edge {
	ll u,v,w,nxt;
	Edge(ll u_=0,ll v_=0,ll w_=0,ll nxt_=0) {
		u=u_;
		v=v_;
		w=w_;
		nxt=nxt_;
	}
};
ll head[maxn],m;
Edge edge[maxn<<1];
inline void addedge(ll u_,ll v_,ll w_) {
	edge[++m].u=u_;
	edge[m].v=v_;
	edge[m].w=w_;
	edge[m].nxt=head[u_];
	head[u_]=m;
	return ;
}
inline void init() {
	n=read(),s=read();
	for(ll i=1; i<=n-1; ++i) {
		ll u,v,w;
		u=read(),v=read(),w=read();
		addedge(u,v,w);
		addedge(v,u,w);
	}
	return ;
}
ll u,v;
ll max_len=-INF,max_p=0;
void dfs_dia(ll now,ll last,ll len) {
	if(len>max_len) {
		max_len=len;
		max_p=now;
	}
	for(ll i=head[now]; i; i=edge[i].nxt)
		if(edge[i].v!=last)
			dfs_dia(edge[i].v,now,len+edge[i].w);
	return ;
}
bool visit[maxn];
inline void dia() {
	dfs_dia(1,0,0);
	u=max_p;
	visit[u]=1;
	max_len=-INF,max_p=0;
	dfs_dia(u,0,0);
	v=max_p;
	visit[v]=1;
	return ;
}
ll diameter[maxn<<1],cnt;
ll point[maxn<<1],cnt_point;
bool dfs_memset_diameter(ll now,ll find,ll last) {
	if(now==find) return 1;
	for(ll i=head[now]; i; i=edge[i].nxt)
		if(edge[i].v!=last) {
			diameter[++cnt]=edge[i].w;
			point[++cnt_point]=now;
			visit[now]=1;
			if(dfs_memset_diameter(edge[i].v,find,now)) return 1;
			visit[now]=0;
			--cnt,--cnt_point;
		}
	return 0;
}
ll dia_o[maxn];
ll dfs_memset_diao(ll now,ll last,ll len) {
	ll ans=len;
	for(int i=head[now];i;i=edge[i].nxt){
		if(!visit[edge[i].v]&&edge[i].v!=last)
			ans=max(ans,dfs_memset_diao(edge[i].v,now,len+edge[i].w));
	}
	return ans;
}
inline void memset_diao() {
	for(int i=1;i<=cnt_point;++i)
		dia_o[point[i]]=dfs_memset_diao(point[i],0,0);
	return ;
}
struct down_queue {
	ll head,tail;
	ll q[maxn<<1],p[maxn<<1];
	down_queue(ll a=1,ll b=0) {
		head=a;
		tail=b;
		if(a==1&&b==0){
			memset(q,0,sizeof(q));
			ll x=maxn<<1; 
			for(int i=0;i<x;++i)
				p[i]=INF;
		}
	}
	void update(ll x,ll k,ll p_) {
		while(head<=tail&&q[tail]<=k)
			--tail;
		q[++tail]=k;
		p[tail]=p_;
		while(p[head]<x)
			++head;
		return ; 
	}
	ll maxs(ll x){
		while(p[head]<x)
			++head;
		return q[head];
	}
	void clear(){
		head=1,tail=0;
		ll x=maxn<<1;
		for(int i=0;i<x;++i){
			q[i]=0;
			p[i]=INF;
		}
		return ;
	}
};
down_queue q;
ll sum[maxn];
inline void memset_sum(){
	for(int i=1;i<=cnt+2;++i)
		sum[i]=sum[i-1]+diameter[i - 1];
	return ;
}
inline ll query(ll l,ll r){
	if( l > r ) return 0;
	return sum[r]-sum[l];
}
inline ll ruler(){
	ll l=1,r=1;
	ll ans=INF;
	q.clear();
	q.update(l,dia_o[point[r]],r);
	while(1) {
		while(r<cnt_point&&query(l,r)<=s){
			++r;
			q.update(l,dia_o[point[r]],r);
		}
		do{
			++l;
		}while(query(l,r)>s&&l!=r);
		if(l==r&&l==cnt_point) return ans;
		ans=min(ans,max(q.maxs(l),max(query(1,l),query(r,cnt_point))));
	}
}
int main() {
	init();//输入
	dia();//求直径
	//point[++cnt_point ] = u;
	dfs_memset_diameter(v,u,0);//把直径存在数组上
	//point[++cnt_point]=v;

	memset_diao();//求直径上每个点到其他点的最远距离
	memset_sum();//预处理前缀和
	printf("%lld\n",ruler());//尺取输出答案
	return 0;
}