按照常规思路,选一个点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("%dn",ans); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605626.html