代码：
```cpp
#include<iostream>
#include<algorithm>
#include<vector>
#include<cassert>
constexpr int N=200005;
constexpr long long Inf=0x3f3f3f3f3f3f3f3f;
struct edge{
int ver,col;
edge():ver{},col{}{}
edge(int V,int C):ver{V},col{C}{}
};
std::vector<edge> G[N];
int val[N];
int n,m,l,r;
long long ans=-Inf;
namespace Tree_Solve{
bool vis[N];
int all,max_part,rt;
int siz[N];
class SegmentTree{
private:
int n;
struct node{
int ls,rs;
long long val;
node():ls{0},rs{0},val{-Inf}{}
};
node tr[N<<2];
int tot,root;
int new_node(){
tr[++tot]=node();
return tot;
}
int get_ls(node &it){
return it.ls?it.ls:it.ls=new_node();
}
int get_rs(node &it){
return it.rs?it.rs:it.rs=new_node();
}
void updata(int p,int l,int r,const int& x,const long long& val){
if(l==r) return void(tr[p].val=std::max(tr[p].val,val));
const int mid=(l+r)>>1;
x<=mid?updata(get_ls(tr[p]),l,mid,x,val):updata(get_rs(tr[p]),mid+1,r,x,val);
tr[p].val=std::max(tr[get_ls(tr[p])].val,tr[get_rs(tr[p])].val);
}
long long query(int p,int l,int r,const int &L,const int &R){
if(!p) return -Inf;
if(L<=l&&r<=R) return tr[p].val;
const int mid=(l+r)>>1;
if(L<=mid&&R>mid) return std::max(query(tr[p].ls,l,mid,L,R),query(tr[p].rs,mid+1,r,L,R));
return L<=mid?query(tr[p].ls,l,mid,L,R):query(tr[p].rs,mid+1,r,L,R);
}
public:
SegmentTree():root{},n{}{}
void init(int size){
n=size;
root=new_node();
//线段树清空
}
void updata(int x,long long val){
updata(root,1,n,x,val);
}
long long query(int L,int R){
return query(root,1,n,std::max(1,L),std::min(R,n));
}
};
void rt_calc(int u,int fa){//求子树重心
siz[u]=1;
int now=0;
for(edge e:G[u])
if(!vis[e.ver]&&e.ver!=fa)
rt_calc(e.ver,u),siz[u]+=siz[e.ver],now=std::max(now,siz[e.ver]);
if((now=std::max(now,all-siz[u]))<max_part) max_part=now,rt=u;
}
SegmentTree lst,now;
//lst存之前处理到的不同颜色，now是当前颜色
std::vector<std::pair<int,long long>> vec;
std::vector<std::pair<int,long long>> pos;
//vec是现在遍历的子树的点，pos是和现在颜色相同的所有子树的点
std::vector<edge> son;
void work_calc(int u,int fa,int col,int dep,long long dis){
vec.emplace_back(dep,dis);
for(edge e:G[u])
if(!vis[e.ver]&&e.ver!=fa)
work_calc(e.ver,u,e.col,dep+1,dis+(e.col==col?0:val[e.col]));
}
void solve(int u){
vis[u]=1;
son.clear();
for(edge e:G[u])
if(!vis[e.ver])
son.emplace_back(e);
std::sort(son.begin(),son.end(),[](edge x,edge y)->bool{
return x.col<y.col;
});
int lst_col={-1};
lst.init(all);
now.init(all);
pos.clear();
//排序之后依次处理
for(auto e:son){
if(~lst_col){
vec.clear();
work_calc(e.ver,u,e.col,1,val[e.col]);
if(e.col==lst_col){
for(auto it:vec)
ans=std::max({ans,lst.query(l-it.first,r-it.first)+it.second,now.query(l-it.first,r-it.first)+it.second-val[e.col]});
for(auto it:vec)
now.updata(it.first,it.second),pos.emplace_back(it.first,it.second);
}
else{
for(auto it:pos)
lst.updata(it.first,it.second);
pos.clear();
for(auto it:vec)
ans=std::max(ans,lst.query(l-it.first,r-it.first)+it.second);
now.init(siz[u]);
for(auto it:vec)
now.updata(it.first,it.second),pos.emplace_back(it);
}
lst_col=e.col;
}
else{
vec.clear();
work_calc(e.ver,u,e.col,1,val[e.col]);
for(auto it:vec)
now.updata(it.first,it.second),pos.emplace_back(it);
lst_col=e.col;
}
}
for(edge e:G[u])
if(!vis[e.ver])
all=max_part=siz[e.ver],rt_calc(e.ver,u),solve(rt);
}
void solve(void){
all=max_part=n;
rt_calc(1,0),solve(rt);
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr),std::cout.tie(nullptr);
std::cin>>n>>m>>l>>r;
for(int i=1;i<=m;++i) std::cin>>val[i];
for(int i=1,u,v,w;i<n;++i)
std::cin>>u>>v>>w,G[u].emplace_back(v,w),G[v].emplace_back(u,w);
Tree_Solve::solve();
std::cout<<ans;
return 0;
}
```
by LQ2024 @ 2023-05-28 12:09:09
找到原因了，没有判断整条路径都在一棵子树下的情况……
~~这都不卡的吗……~~
by LQ2024 @ 2023-05-28 12:57:32
@[LQ2024](/user/673643) 笑死，最开始我一个样例没过，但90分
by zyxawa @ 2023-05-28 13:35:25
@[zyxawa](/user/673294) azazaz
by LQ2024 @ 2023-05-28 13:52:52
?
by yz_by @ 2023-05-29 18:53:48
@[LQ2024](/user/673643) 这下样例的数据最强了（x）
by Remilia1023 @ 2023-08-23 15:43:07
@[Remilia1023](/user/625206) 正确的，中肯的，一针见血的。
by LQ2024 @ 2023-08-23 16:30:30