c/c++语言开发共享[BJOI2017] 树的难题

按照常规思路，选一个点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; }