90pts wa on 6

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5,INF=-1e18;
int n,m,l,r,c[N],u,v,w,root,del[N],siz[N],ans,len[N],val[N],tot;
struct node{
	int to,col;
}tmp[N];
bool cmp(node u,node v){
	return u.col<v.col;
}
vector<node>ve[N];
struct segtree{
	int tree[N*4],tag[N*4];
	void pushup(int u){
		tree[u]=max(tree[u*2],tree[u*2+1]);
		return ;
	}
	void pushdown(int u){
		if(!tag[u]) return ;
		tag[u*2]=1;
		tag[u*2+1]=1;
		tree[u]=INF;
		tag[u]=0;
		return ; 
	}
	int query(int u,int L,int R,int l,int r){
		if(L>=l && R<=r){
			return tree[u];
		}
		int mid=(L+R)>>1,mx=INF;
		pushdown(u);
		if(mid>=l) mx=query(u*2,L,mid,l,r);
		if(mid+1<=r) mx=max(mx,query(u*2+1,mid+1,R,l,r));
		return mx;
	}
	void update(int u,int L,int R,int p,int val){
		if(L==R){
			tree[u]=max(tree[u],val);
			return ;
		}
		int mid=(L+R)>>1;
		pushdown(u);
		if(p<=mid) update(u*2,L,mid,p,val);
		else update(u*2+1,mid+1,R,p,val);
		pushup(u);
		return ; 
	}
}T1,T2;
void dfs1(int x,int fa){
	int mx=1;
	siz[x]=1;
	for(int i=0;i<ve[x].size();i++){
		if(ve[x][i].to==fa || del[ve[x][i].to]) continue;
		dfs1(ve[x][i].to,x);
		if(root) return ;
		mx=max(mx,siz[ve[x][i].to]);
		siz[x]+=siz[ve[x][i].to];
	}
	mx=max(mx,n-siz[x]);
	if(mx<=n/2){
		root=x;
		siz[fa]=n-siz[x];
	}
	return ;
}
void dfs2(int x,int fa,int col,int sum,int dep,int delet){
	if(dep>r) return ;
	len[x]=dep;
	val[x]=sum;
	if(dep>=l) ans=max(ans,sum);
	if(dep<r) ans=max(ans,T1.query(1,1,n-1,max(1ll,l-dep),min(n-1,r-dep))+sum);
	if(dep<r) ans=max(ans,T2.query(1,1,n-1,max(1ll,l-dep),min(n-1,r-dep))+sum-delet);
	for(int i=0;i<ve[x].size();i++){
		if(ve[x][i].to==fa || del[ve[x][i].to]) continue;
		dfs2(ve[x][i].to,x,ve[x][i].col,sum+c[ve[x][i].col]*(ve[x][i].col!=col),dep+1,delet);
	}
	return ;
}
void dfs3(int x,int fa,int kind){
	if(!len[x]) return ;
	if(kind==1) T1.update(1,1,n-1,len[x],val[x]);
	else T2.update(1,1,n-1,len[x],val[x]);
	for(int i=0;i<ve[x].size();i++){
		if(ve[x][i].to==fa || del[ve[x][i].to]) continue;
		dfs3(ve[x][i].to,x,kind);
	}
	return ;
}
void run(int x){
	del[x]=1;
	for(int i=1;i<=4*n;i++){
		T1.tree[i]=INF;
		T1.tag[i]=0;
		T2.tree[i]=INF;
		T2.tag[i]=0;
	}
	tot=0;
	for(int i=0;i<ve[x].size();i++){
		if(del[ve[x][i].to]) continue;
		tmp[++tot].to=ve[x][i].to;
		tmp[tot].col=ve[x][i].col;
	}
	sort(tmp+1,tmp+tot+1,cmp);
	int pre=1;
	for(int i=1;i<=tot;i++){
		int to=tmp[i].to,col=tmp[i].col;
		if(col!=tmp[i-1].col && i!=1){
			for(int j=pre;j<=i-1;j++) dfs3(tmp[j].to,x,1);
			T2.tag[1]=1;
			pre=i;
		}
		dfs2(to,x,col,c[col],1,c[col]);
		dfs3(to,x,2);
	}
	for(int i=0;i<ve[x].size();i++){
		if(del[ve[x][i].to]) continue;
		root=0;
		n=siz[ve[x][i].to];
		dfs1(ve[x][i].to,x);
		run(root);
	}
	return ;
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>m>>l>>r;
	for(int i=1;i<=m;i++){
		cin>>c[i];
	}
	for(int i=1;i<=n-1;i++){
		cin>>u>>v>>w;
		ve[u].push_back({v,w});
		ve[v].push_back({u,w});
	}
	dfs1(1,0);
	ans=INF;
	run(root); 
	cout<<ans<<'\n';
	return 0;
}