题目描述
给你一棵 n 个点的无根树。
树上的每条边具有颜色。一共有 m 种颜色，编号为 1 到 m。第 i 种颜色的权值为 ci。
对于一条树上的简单路径，路径上经过的所有边按顺序组成一个颜色序列，序列可以划
分成若干个相同颜色段。定义路径权值为颜色序列上每个同颜色段的颜色权值之和。
请你计算，经过边数在 l 到 r 之间的所有简单路径中，路径权值的最大值。
题解
如果没有颜色这种东西的话，看到l~r的限制，就容易想到点分治+单调队列维护。
我们的单调队列的作用其实就是合并两颗子树。
考虑有如果我们准备合并的那两颗子树的第一条边颜色相同，那么答案应当再去减去一个边权。
所以我们得对于每种颜色分别维护。
但是我们还需要保证合并的复杂度。
这时候我们考虑对于颜色相同的子树，我们把它们放在一起按照最大深度从小到大处理，这样能够保证它的复杂度是线性的。
但是多个颜色怎么处理。
观察到我们合并两个不同的颜色可以看做是两个桶在合并，所以对于颜色我们按照这个颜色的最大深度排个序就好了。
代码
我要再把while写成if就去cs。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define N 200002
using namespace std;
int head[N],tot,h,t,q[N],dp[N],size[N],root,sum,deep[N],maxdeep,su[N];
int maxl,minl,que[N],colmaxdeep[N],n,m,cal[N],ans,c[N];
bool vis[N],visit[N];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
struct edge{int n,to,l;}e[N<<];
struct node{
int id,col,dep;
inline bool operator <(const node &b)const{
if(col!=b.col){
// if(su[col]!=su[b.col])return su[col]<su[b.col];
if(colmaxdeep[col]!=colmaxdeep[b.col])return colmaxdeep[col]<colmaxdeep[b.col];
else return col<b.col;
}
else return dep<b.dep;
}
}b[N];
int tong[N],_tong[N];
inline void add(int u,int v,int l){
e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l;
}
void getroot(int u,int fa){
dp[u]=;size[u]=;
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
int v=e[i].to;
getroot(v,u);
size[u]+=size[v];
dp[u]=max(dp[u],size[v]);
}
dp[u]=max(dp[u],sum-size[u]);
if(dp[u]<dp[root])root=u;
}
void getsize(int u,int fa){
size[u]=;
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
int v=e[i].to;
getsize(v,u);
size[u]+=size[v];
}
}
void getdeep(int u,int fa,int val,int lastcol){
cal[u]=val;maxdeep=max(maxdeep,deep[u]);
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
int v=e[i].to;deep[v]=deep[u]+;
getdeep(v,u,e[i].l==lastcol?val:val+c[e[i].l],e[i].l);
}
}
void getcalc(int u,int fa){
tong[deep[u]]=max(tong[deep[u]],cal[u]);
for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!vis[e[i].to]){
int v=e[i].to;deep[v]=deep[u]+;
getcalc(v,u);
}
}
inline void _ins(int x){
while(h<=t&&_tong[q[t]]<=_tong[x])t--;
q[++t]=x;
}
inline void ins(int x){
while(h<=t&&tong[q[t]]<=tong[x])t--;
q[++t]=x;
}
inline void calc(int u){
int clsum=;vis[u]=;
for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){
int v=e[i].to;maxdeep=;
deep[v]=;getdeep(v,u,c[e[i].l],e[i].l);
b[++clsum]=node{v,e[i].l,maxdeep};
colmaxdeep[e[i].l]=maxdeep;su[e[i].l]++;
}
int nowmaxdeep=,summaxdeep=;
sort(b+,b+clsum+);
for(int o=;o<=clsum+;++o){
int v=b[o].id;
if(b[o].col!=b[o-].col){
summaxdeep=max(summaxdeep,nowmaxdeep);
h=t=;q[h]=;int p=;
for(int i=nowmaxdeep;i>=;--i){
while(p+i<maxl&&p<summaxdeep){p++;_ins(p);}
while(h<=t&&q[h]+i<minl)h++;if(h<=t)ans=max(ans,tong[i]+_tong[q[h]]);
}
for(int j=;j<=nowmaxdeep;++j)_tong[j]=max(_tong[j],tong[j]),tong[j]=-1e9;
nowmaxdeep=;
}
if(o>clsum)break;
q[h=t=]=v;visit[v]=;que[]=;
while(h<=t){
int u=q[h++];
que[++que[]]=u;
for(int i=head[u];i;i=e[i].n){
int v=e[i].to;
if(!vis[v]&&!visit[v])q[++t]=v,visit[v]=;
}
}
h=;t=;int p=;
for(int i=que[];i>=;--i){
int x=que[i];visit[x]=;
while(p+deep[x]<maxl&&p<nowmaxdeep){p++;ins(p);}
while(h<=t&&q[h]+deep[x]<minl)h++;
if(h<=t)ans=max(ans,cal[x]+tong[q[h]]-c[b[o].col]);
}
getcalc(v,u);
nowmaxdeep=max(nowmaxdeep,b[o].dep);
}
for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to])colmaxdeep[e[i].l]=,su[e[i].l]=;
// cout<<summaxdeep<<endl;
for(int i=;i<=summaxdeep;++i)tong[i]=_tong[i]=-1e9;
}
void solve(int u){
calc(u);
for(int i=head[u];i;i=e[i].n)if(!vis[e[i].to]){
int v=e[i].to;
root=n+;sum=size[v];
getroot(v,u);getsize(root,);
solve(root);
}
}
int main(){
n=rd();m=rd();minl=rd();maxl=rd();
for(int i=;i<=n;++i)tong[i]=_tong[i]=-1e9;
ans=-1e9;
for(int i=;i<=m;++i)c[i]=rd();
int u,v,w;
for(int i=;i<n;++i){
u=rd();v=rd();w=rd();
add(u,v,w);add(v,u,w);
}
sum=n;root=n+;dp[root]=n+;
getroot(,);getsize(root,);
solve(root);
printf("%d\n",ans);
return ;
}