[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("%d\n",ans);
    return 0;
}