淀粉汁+线段树做法

using namespace std;
#define ll long long
#define inf 1e18
#define MAXN 1000010
#define pir pair<ll,ll>
#define mp make_pair
#define debug cout<<"flyfree\n";
// By flyfreemrn
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct node_sgt{
	ll l[MAXN*4],r[MAXN*4],maxz[MAXN*4];
	void build(ll lz,ll rz,ll now){
		l[now]=lz,r[now]=rz,maxz[now]=-inf;
		if(lz==rz)return;
		ll mid=(lz+rz)/2;
		build(lz,mid,now*2);
		build(mid+1,rz,now*2+1);
	}
	ll _find(ll lz,ll rz,ll now){
		if(l[now]>=lz&&r[now]<=rz)return maxz[now];
		ll mid=(l[now]+r[now])/2,ans=-inf;
		if(lz<=mid)ans=max(ans,_find(lz,rz,now*2));
		if(rz>mid)ans=max(ans,_find(lz,rz,now*2+1));
		return ans;
	}
	void insert(ll pos,ll val,ll now){
		maxz[now]=max(maxz[now],val);
		if(l[now]==r[now])return;
		ll mid=(l[now]+r[now])/2;
		if(pos<=mid)insert(pos,val,now*2);
		else insert(pos,val,now*2+1);
	}
	void clear(ll pos,ll now){
		maxz[now]=-inf;
		if(l[now]==r[now])return;
		ll mid=(l[now]+r[now])/2;
		if(pos<=mid)clear(pos,now*2);
		else clear(pos,now*2+1);
	}
}sgt1,sgt2;
bool used[MAXN];
vector<pir> vec[MAXN];
ll n,m,l,r,min_siz,id,ans=-inf;
ll siz[MAXN],maxu[MAXN],val[MAXN],dep[MAXN],len[MAXN];
vector<ll> q,sam;
void mk_siz(ll now,ll fa){
	siz[now]=1;
	for(int i=0;i<vec[now].size();i++){
		ll y=vec[now][i].second;
		if(used[y]||y==fa)continue;
		mk_siz(y,now);
		siz[now]+=siz[y];
	}
}
void _find(ll now,ll fa,ll tot){//当前节点，父节点，总点数 
	maxu[now]=tot-siz[now];
	for(int i=0;i<vec[now].size();i++){
		ll y=vec[now][i].second;
		if(y==fa||used[y])continue;
		_find(y,now,tot);
		maxu[now]=max(maxu[now],siz[y]);
	}
	if(maxu[now]<min_siz)min_siz=maxu[now],id=now;
}
void dfs(ll now,ll fa,ll _dep,ll _len,ll _col){//当前点，父节点，深度，长度，颜色 
	dep[now]=_dep,len[now]=_len;
	q.push_back(now);
	for(int i=0;i<vec[now].size();i++){
		ll y=vec[now][i].second,col=vec[now][i].first;
		if(used[y]||y==fa)continue;
		dfs(y,now,_dep+1,(_col==col)?_len:_len+val[col],col);
	}
}
void clear(ll now,ll fa){
	if(dep[now]<=r)sgt1.clear(dep[now],1);
	dep[now]=len[now]=0;
	for(int i=0;i<vec[now].size();i++){
		ll y=vec[now][i].second;
		if(used[y]||y==fa)continue;
		clear(y,now);
	}
}
void solve(ll now){
	cout<<"now:"<<now<<endl;
//	debug;
	ll it=0;
	for(int i=1;i<=m;i++){
//		cout<<i<<endl;
		while(it<vec[now].size()){
			if(vec[now][it].first<=i){
//				cout<<it<<" "<<vec[now].size()<<" "<<vec[now][it].second<<endl;
				ll s=vec[now][it].second;
				it++;
				if(used[s])continue;
//				debug;
//				cout<<it<<endl;
				dfs(s,now,1,0,i);
//				debug;
				for(int j=0;j<q.size();j++){//查找答案 
					ll y=q[j];
					sam.push_back(y);
					if(used[y]||dep[y]>r)continue;
					ll ans1=sgt1._find(max(0ll,l-dep[y]),r-dep[y],1),ans2=sgt2._find(max(0ll,l-dep[y]),r-dep[y],1);
					//ans1不同颜色答案,ans2同颜色答案 
					ans=max(ans,max(ans1,ans2)+len[y]+val[i]);
				}
//				debug;
				for(int j=0;j<q.size();j++){
					ll y=q[j];
					if(used[y]||dep[y]>r)continue;
					sgt2.insert(dep[y],len[y],1);
					//修改 
				}
				q.clear();
//				it++;
			}else break;
		}
//		debug;
		for(int j=0;j<sam.size();j++){
			ll y=sam[j];
			if(used[y]||dep[y]>r)continue;
			sgt1.insert(dep[y],len[y]+val[i],1);//线段树1修改 
			sgt2.clear(dep[y],1);//线段树2清空 
		}
		sgt2.insert(0,0,1);
//		cout<<i<<endl;
		sam.clear();
	}
	for(int i=0;i<vec[now].size();i++){//线段树1清空 
		ll y=vec[now][i].second;
		if(used[y])continue;
		clear(y,now);
	} 
	sgt1.insert(0,0,1);
//	debug;
	used[now]=true;
	for(int i=0;i<vec[now].size();i++){
		ll y=vec[now][i].second;
		if(used[y])continue;
		mk_siz(y,now);
		min_siz=inf,id=0;
		_find(y,now,siz[y]);
		solve(id);
	}
}
int main(){
	n=read(),m=read(),l=read(),r=read();
	sgt1.build(0,n,1),sgt2.build(0,n,1);
	sgt1.insert(0,0,1),sgt2.insert(0,0,1);
	for(int i=1;i<=m;i++)val[i]=read();
	for(int i=1;i<n;i++){
		ll x=read(),y=read(),z=read();
		vec[x].push_back(mp(z,y));
		vec[y].push_back(mp(z,x));
	}
	for(int i=1;i<=n;i++)sort(vec[i].begin(),vec[i].end());
	mk_siz(1,1);
	min_siz=inf,id=0;
	_find(1,1,siz[1]);
	solve(id);
	cout<<ans;
	return 0;
}```