题目传送门
分析路径问题考虑点分治
对于一个分治中心，我们可以很容易地得到从它开始的一条路径的价值和长度
问题就是如何将不同的路径合并
很显然，对于同一个子树中的所有路径，它们起始的颜色是相同的
因此我们可以将一个节点的所有子结点按照颜色排序
这个可以在建图之前处理好
然后开两个权值线段树，一棵存储与当前节点起始颜色相同的所有路径，另一棵存储不同的所有路径
当节点的颜色改变时，把相同的那一堆合并到另一堆即可
时间复杂度 \(nlog^2n\)
代码 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<vector> #define rg register inline int read(){ rg int x=0,fh=1; rg char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') fh=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*fh; } const int maxn=4e5+5; int h[maxn],tot=1,n,m,lef,rig,val[maxn]; struct asd{ int to,nxt,val; }b[maxn]; void ad(rg int aa,rg int bb,rg int cc){ b[tot].to=bb; b[tot].nxt=h[aa]; b[tot].val=cc; h[aa]=tot++; } int siz[maxn],maxsiz[maxn],rt,totsiz; bool vis[maxn]; void getroot(rg int now,rg int lat){ siz[now]=1,maxsiz[now]=0; for(rg int i=h[now];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(u==lat || vis[u]) continue; getroot(u,now); siz[now]+=siz[u]; maxsiz[now]=std::max(maxsiz[now],siz[u]); } maxsiz[now]=std::max(maxsiz[now],totsiz-siz[now]); if(maxsiz[now]<maxsiz[rt]) rt=now; } struct trr{ int lch,rch,val; trr(){ lch=rch=0; val=-0x3f3f3f3f;//一定要初始化成无穷小 } }tr[maxn*40]; int cnt,rt1,rt2,tp,ans=-0x3f3f3f3f; void push_up(rg int da){ tr[da].val=std::max(tr[tr[da].lch].val,tr[tr[da].rch].val); } int xg(rg int da,rg int l,rg int r,rg int wz,rg int val){ if(!da){ da=++cnt; tr[da].lch=tr[da].rch=0,tr[da].val=-0x3f3f3f3f; } if(l==r){ tr[da].val=std::max(tr[da].val,val); return da; } rg int mids=(l+r)>>1; if(wz<=mids) tr[da].lch=xg(tr[da].lch,l,mids,wz,val); else tr[da].rch=xg(tr[da].rch,mids+1,r,wz,val); push_up(da); return da; } int bing(rg int aa,rg int bb,rg int l,rg int r){ if(!aa || !bb) return aa+bb; if(l==r){ tr[aa].val=std::max(tr[aa].val,tr[bb].val); tr[bb].val=-0x3f3f3f3f; return aa; } rg int mids=(l+r)>>1; tr[aa].lch=bing(tr[aa].lch,tr[bb].lch,l,mids); tr[aa].rch=bing(tr[aa].rch,tr[bb].rch,mids+1,r); push_up(aa); return aa; } int cx(rg int da,rg int l,rg int r,rg int nl,rg int nr){ if(!da || l>r) return -0x3f3f3f3f; if(l>=nl && r<=nr) return tr[da].val; rg int mids=(l+r)>>1,nans=-0x3f3f3f3f; if(nl<=mids) nans=std::max(nans,cx(tr[da].lch,l,mids,nl,nr)); if(nr>mids) nans=std::max(nans,cx(tr[da].rch,mids+1,r,nl,nr)); return nans; } struct jie{ int val,dep; jie(){} jie(rg int aa,rg int bb){ val=aa,dep=bb; } }sta[maxn]; bool cmp(rg jie aa,rg jie bb){ return aa.val>bb.val; } std::vector<jie> g[maxn]; void dfs(rg int now,rg int lat,rg int nval,rg int ndep,rg int latcol){ if(ndep>rig) return; sta[++tp]=jie(nval,ndep); for(rg int i=h[now];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(u==lat || vis[u]) continue; dfs(u,now,(latcol==b[i].val)?nval:nval+val[b[i].val],ndep+1,b[i].val); } } void solve(rg int now){ vis[now]=1; rt1=rt2=cnt=0; rg int latcol=0,jud=0; for(rg int i=h[now];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(!vis[u]){ tp=jud=0; dfs(u,now,val[b[i].val],1,b[i].val); if(b[i].val==latcol) jud=1; else { rt1=bing(rt1,rt2,1,n); rt2=0; } for(rg int j=1;j<=tp;j++){ if(jud) ans=std::max(ans,cx(rt2,1,n,std::max(1,lef-sta[j].dep),rig-sta[j].dep)+sta[j].val-val[latcol]); ans=std::max(ans,cx(rt1,1,n,std::max(1,lef-sta[j].dep),rig-sta[j].dep)+sta[j].val); if(sta[j].dep>=lef && sta[j].dep<=rig) ans=std::max(ans,sta[j].val); } for(rg int j=1;j<=tp;j++) rt2=xg(rt2,1,n,sta[j].dep,sta[j].val); latcol=b[i].val; } } for(rg int i=h[now];i!=-1;i=b[i].nxt){ rg int u=b[i].to; if(!vis[u]){ totsiz=siz[u],rt=0; getroot(u,now); solve(rt); } } } int main(){ memset(h,-1,sizeof(h)); n=read(),m=read(),lef=read(),rig=read(); for(rg int i=1;i<=m;i++) val[i]=read(); rg int aa,bb,cc; for(rg int i=1;i<n;i++){ aa=read(),bb=read(),cc=read(); g[aa].push_back(jie(cc,bb)),g[bb].push_back(jie(cc,aa)); } for(rg int i=1;i<=n;i++) std::sort(g[i].begin(),g[i].end(),cmp); for(rg int i=1;i<=n;i++){ for(rg int j=0;j<g[i].size();j++){ ad(i,g[i][j].dep,g[i][j].val); } } maxsiz[0]=0x3f3f3f3f,rt=0,totsiz=n; getroot(1,0); solve(rt); printf("%d\n",ans); return 0; }