[BJOI2017]树的难题

LG传送门

点分治+线段树合并。

我不会写单调队列，所以就写了好写的线段树。

考虑对于每一个分治中心，把出边按颜色排序，这样就能把颜色相同的子树放在一起处理。用一棵动态开点线段树维护颜色不同的子树的信息，另一棵动态开点线段树维护颜色相同的子树的信息，同时按照题目要求更新答案。当子树颜色变化时，就把第二棵线段树合并到第一棵里面去就好了。

代码实现有点繁琐，我调了很久。。。

#include<cstdio>

#include<cctype>

#include<cstring>

#include<algorithm>

#include<vector>

#define R register

#define I inline

#define Z first

#define Y second

using namespace std;

const int S=200003,M=6000003,inf=0x3f3f3f3f;

char buf[1000000],*p1,*p2;

I char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,S,stdin),p1==p2)?EOF:*p1++;}

I int rd(){

    R int f=0,b=1; R char c=gc();

    while((c<48||c>57)&&c!=45) c=gc();

    if(c==45) b=0,c=gc();

    while(c>47&&c<58) f=f*10+(c^48),c=gc();

    return b?f:~f+1;

}

vector<pair<int,int> > g[S];

struct T{int l,r,f;}a[M];

int c[S],s[S],t[S],h[S],v[S],n,m,e,L,U,u,r,o=-inf,A,B;

I int max(int x,int y){return x>y?x:y;}

I void add(int x,int y,int z){g[x].push_back(make_pair(z,y)),++s[x];}

I void ini(){a[++e].f=-inf,a[e].l=a[e].r=0;}

int mrg(int k,int t){

    if(!k) return t;

    if(!t) return k;

    a[k].f=max(a[k].f,a[t].f),a[k].l=mrg(a[k].l,a[t].l),a[k].r=mrg(a[k].r,a[t].r);

    return k;

}

void ins(int &k,int l,int r,int x,int v){

    if(!k) ini(),k=e;

    if(l==r){a[k].f=max(a[k].f,v); return ;}

    R int m=l+r>>1;

    if(x<=m) ins(a[k].l,l,m,x,v);

    else ins(a[k].r,m+1,r,x,v);

    a[k].f=max(a[a[k].l].f,a[a[k].r].f);

}

int qry(int k,int l,int r,int x,int y){

    if(!k) return -inf;

    if(x<=l&&r<=y) return a[k].f;

    R int m=l+r>>1,o=-inf;

    if(x<=m) o=max(o,qry(a[k].l,l,m,x,y));

    if(m<y) o=max(o,qry(a[k].r,m+1,r,x,y));

    return o;

}

void gsz(int x,int f){

    t[x]=1;

    for(R int i=0,y;i<s[x];++i)

        if(!v[y=g[x][i].Y]&&y^f)

            gsz(y,x),t[x]+=t[y];

}

void grt(int x,int f,int a){

    R int i,y,m=0;

    for(i=0;i<s[x];++i)

        if(!v[y=g[x][i].Y]&&y^f)

            grt(y,x,a),m=max(m,t[y]);

    m=max(m,a-t[x]);

    if(m<u) u=m,r=x;

}

void dfs(int x,int f,int r,int l,int d){

    if(l>U) return ;

    h[l]=max(h[l],d);

    for(R int i=0,y,z;i<s[x];++i)

        if(!v[y=g[x][i].Y]&&y^f)

            z=g[x][i].Z,dfs(y,x,z,l+1,z^r?d+c[z]:d);

}

void dac(int x){

    R int i,j,y,z,l;

    e=A=B=0,u=n,gsz(x,0),grt(x,0,t[x]),gsz(r,0),v[r]=1,l=r;

    for(i=0;i<s[r];++i)

        if(!v[y=g[r][i].Y]){

            z=g[r][i].Z,memset(h,-0x3f,sizeof(int)*(t[y]+1));

            if(B&&z^g[r][i-1].Z)

                A=mrg(A,B),B=0;

            dfs(y,r,z,1,c[z]);

            for(j=1;j<=t[y]&&j<U&&h[j]^h[0];++j)

                o=max(max(o,L<=j&&j<=U?h[j]:-inf),max(qry(A,1,U,max(1,L-j),U-j),qry(B,1,U,max(1,L-j),U-j)-c[z])+h[j]);

            o=max(o,h[U]);

            for(j=1;j<=t[y]&&j<U&&h[j]^h[0];++j)

                ins(B,1,U,j,h[j]);

        }

    for(i=0;i<s[l];++i)

        if(!v[y=g[l][i].Y])

            dac(y);

}

int main(){

    R int i,x,y,z;

    n=rd(),m=rd(),L=rd(),U=rd();

    for(i=1;i<=m;++i)

        c[i]=rd();

    for(i=1;i<n;++i)

        x=rd(),y=rd(),z=rd(),add(x,y,z),add(y,x,z);

    for(i=1;i<=n;++i)

        sort(g[i].begin(),g[i].end());

    memset(h,-0x3f,sizeof h),a[0].f=-inf,dac(1),printf("%d",o);

    return 0;

}