按照常规思路，选一个点x作为分治中心，拼接x出发到子树各点的路径。对于拼接时两段接口处（即x连出的那条边，若没有，设为0号边：颜色为0，长度为0，到达0号儿子）颜色的影响，可以记录每段的路径权值、边数以及该段的接口，将所有的路径以接口颜色为第一关键字，接口编号为第二关键字排序。显然，对于同一接口的路径必为连续的一段序列。这样枚举每个路径，找到之前出现的符合边数和的要求的最大的路径权值即可。用两颗线段树维护，一棵维护与本路径不同颜色的，一颗维护与本路径颜色相同但接口不同的（因为简单路径的拼接要满足两个端点不在同一个子树内）。
时间复杂度 O(nlognlogn)
常数巨大，需要吸氧和c++11
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int M=4e5+10;
const int inf=0x3f3f3f3f;
int n,m,L,R;
int c[N],head[N],to[M],clr[M],last[M];
int sum,top,rt,fiz[N],siz[N];
bool ban[N];
struct Seg {
int dis,num,bel;
} p[N];
struct Rmq {
#define ls (x<<1)
#define rs (x<<1|1)
int val[N<<2];
bool tag[N<<2];
void clear() {
val[1]=-inf;
tag[1]=1;
}
void pushDown(int x) {
val[ls]=-inf,tag[ls]=1;
val[rs]=-inf,tag[rs]=1;
tag[x]=0;
}
void modify(int x,int l,int r,int p,int w) {
if(l==r) return void(val[x]=w);
int mid=(l+r)>>1;
val[x]=max(val[x],w);
if(tag[x]) pushDown(x);
if(p<=mid) modify(ls,l,mid,p,w);
else modify(rs,mid+1,r,p,w);
}
int query(int x,int l,int r,int L,int R) {
if(L<=l && r<=R) return val[x];
int mid=(l+r)>>1, ret=-inf;
if(tag[x]) return ret;
if(L<=mid) ret=max(ret,query(ls,l,mid,L,R));
if(mid<R) ret=max(ret,query(rs,mid+1,r,L,R));
return ret;
}
inline void modify(int p,int w) {
modify(1,1,n+1,p+1,w);
}
inline int query(int L,int R) {
if(R<L || R<0) return -inf;
return query(1,1,n+1,L+1,R+1);
}
#undef ls
#undef rs
} A,B;
void addEdge(int x,int y,int c) {
static int cnt=0;
to[++cnt]=y;
clr[cnt]=c;
last[cnt]=head[x];
head[x]=cnt;
}
void getRoot(int x,int pa) {
fiz[x]=0,siz[x]=1;
for(int i=head[x]; i; i=last[i]) {
if(to[i]==pa||ban[to[i]]) continue;
getRoot(to[i],x);
siz[x]+=siz[to[i]];
fiz[x]=max(fiz[x],siz[to[i]]);
}
fiz[x]=max(fiz[x],sum-siz[x]);
if(fiz[x]<fiz[rt]) rt=x;
}
int ans=-2e9;
void getDis(int x,int pa,int dis,int num,int pClr,int bel) {
p[++top]=(Seg){dis,num,bel};
for(int i=head[x]; i; i=last[i]) {
if(to[i]==pa||ban[to[i]]) continue;
if(pClr==clr[i]) getDis(to[i],x,dis,num+1,clr[i],bel);
else getDis(to[i],x,dis+c[clr[i]],num+1,clr[i],bel);
}
}
void calc(int x) {
p[top=1]=(Seg){0,0,0};
for(int i=head[x]; i; i=last[i]) {
if(ban[to[i]]) continue;
getDis(to[i],x,c[clr[i]],1,clr[i],i);
}
sort(p+1,p+top+1,[=](Seg x,Seg y){
if(clr[x.bel]!=clr[y.bel]) return clr[x.bel]<clr[y.bel];
return x.bel<y.bel;
});
A.clear();
B.clear();
for(int l=1,r; l<=top; l=r+1) {
for(r=l; r<top && clr[p[l].bel]==clr[p[r+1].bel]; ++r);
for(int x=l,y; x<=r; x=y+1) {
for(y=x; y<r && p[x].bel==p[y+1].bel; ++y);
if(x!=l) for(int i=x; i<=y; ++i)
ans=max(ans,p[i].dis+B.query(L-p[i].num,R-p[i].num)-c[clr[p[i].bel]]);
for(int i=x; i<=y; ++i) B.modify(p[i].num,p[i].dis);
}
B.clear();
if(l!=1) for(int i=l; i<=r; ++i)
ans=max(ans,p[i].dis+A.query(L-p[i].num,R-p[i].num));
for(int i=l; i<=r; ++i) A.modify(p[i].num,p[i].dis);
}
}
void solveAt(int x) {
ban[x]=true;
calc(x);
for(int i=head[x]; i; i=last[i]) {
if(ban[to[i]]) continue;
rt=0;
sum=siz[to[i]];
getRoot(to[i],x);
solveAt(rt);
}
}
int main() {
scanf("%d%d%d%d",&n,&m,&L,&R);
for(int i=1; i<=m; ++i) scanf("%d",&c[i]);
for(int x,y,c,i=n; --i; ) {
scanf("%d%d%d",&x,&y,&c);
addEdge(x,y,c);
addEdge(y,x,c);
}
rt=0;
sum=n;
fiz[0]=2e9;
getRoot(1,0);
solveAt(rt);
printf("%d
",ans);
return 0;
}