According to the general idea, select a point x as the center of divide and conquer, and splice x to start the path from each point of the subtree. For the influence of color at the interface of two segments (i.e. the edge connected by X, if not, set as edge 0: color is 0, length is 0, reaching the son of 0), the path weight, edge number of each segment and the interface of the segment can be recorded. All paths are sorted by interface color as the first key and interface number as the second key. Obviously, the path to the same interface must be a continuous sequence. In this way, enumerate each path, and find the maximum path weight that meets the requirements of the sum of sides. Two line segment trees are used for maintenance, one for maintenance with different colors of the path, and one for maintenance with the same color of the path but different interfaces (because the splicing of simple paths should satisfy that two endpoints are not in the same subtree).

Time complexity O (nlognlog n)

Constant is huge, need oxygen and 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\n",ans);
    return 0;
}