题目大意

给你一棵带点权的树和许多条路径。

然后有一堆询问，每次询问一段区间内所有路径的并的点权和。

---

思考历程

比赛时看到这题，已经没有什么时间了。

果断地打了个树链剖分加莫队，信心满满地觉得自己能过。

维护的时候类似于扫描线。

才打了20分钟。

在比赛的最后一刻，我突然意识到这个做法的时间复杂度非常大。

甚至不如暴力。

于是TLE了……

---

正解

其实题目有个比较显而易见的方法（然而我居然没有想到）。按照询问右端点排个序，在所有路径中从左到右扫。对于每个点，记录最后被覆盖的时间。

在树状数组维护每条边覆盖的点，并且这些点最后一次是被这条边覆盖的，满足这些条件的点的权值和。（也就是说，每个点向最后被覆盖的时间的那个位置，贡献它的点权）

现在考虑如何维护这个东西。

题解中有个比较奇妙的做法：

假设这棵树是一条链（如果不是一条链就树链剖分）。

现在每次要覆盖一个区间。

其实这就是一个区间染色的问题。每次覆盖的区间所有点的颜色必然就会被修改。

于是就可以用传说中的珂朵莉树……

其实题解也没有说是这个数据结构，不过实际上就是。

珂朵莉树的核心思想是，将相同状态的点合并成区间，一同处理。

至于具体实现，常规是用set，或者如果你喜欢也可以打平衡树或线段树之类的。每个节点维护的是一个相同状态的点组成的一个区间。

在平常的题目中，珂朵莉树要满是数据随机才可以达到\(O(n \lg n)\)的时间复杂度。但这题不一样。

在这题中，每个颜色相同的区间合在一起处理。在染色的时候，就要将这个区间覆盖的所有区间连同它们的贡献删去，再加入这个区间（相交的区间就分裂一下）。

显然，每次加入的区间新的区间个数是一个；并且它覆盖原来的区间之后，原来的那些区间都要被暴力删除，而它们只会被暴力删除一次。

所以这题的时间复杂度是有保障的，就是\(O(n \lg n)\)。

树链剖分之后时间复杂度要乘个\(\lg n\)。

或者还有一种非常简单的而且常数很小的方法：

直接上\(LCT\)。\(LCT\)上的每条链表示的是颜色相同的点（不过颜色相同的点不一定在同一条链里面），于是就可以将整条链的贡献在树状数组里面加加减减。

在修改的时候，求出\(LCA\)（不要用\(LCT\)直接求，因为在这里不是可以随便使用access的）。然后将\(LCA\)和它父亲的那条边断掉。

接着access(u)和access(v)。在\(access\)的过程中，同时在树状数组上进行修改。

时间复杂度也是\(O(n \lg^2 n)\)，常数极小，代码简短。

提醒一下：这题是不能mroot的，因为mroot需要用到access，而access是不能随便用的。

还有一种强大的分治做法，不过常数似乎很大。

设当前的大区间为\([L,R]\)。一个询问\([l,r]\)可以分成：\([l,mid]\)和\([mid+1,r]\)两部分。

首先将\([L,R]\)中的所有点建立一棵虚树。时间复杂度是\(O(n \lg n)\)的。

然后先处理\([mid+1,r]\)的路径。显然我们只需要记录每个节点它最早出现的时间，因为询问区间是从中点向两边延伸的。

于是就用传统的并查集染色做法扫过去，并且用树状数组维护一下每一条路径能覆盖到了的所有新点的和。

右边处理完之后就处理左边。先将并查集清空，同样地用并查集染色的做法。不过这次染到的新点就要在树状数组中减去它的贡献，同时用一个变量来存它的贡献。

因为指针一直都往左边移，在左边出现过的就需要在右边加上了。

在这时候同时处理询问，就是用右边树状数组存下的值加上左边这个变量存下的值。

时间复杂度也是\(O(n \lg^2 n)\)

---

代码

\(LCT\)做法

using namespace std;#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define N 100010#define ll long longint n,m,Q;int a[N];ll t[N];#define lowbit(x) ((x)&-(x))inline void add(int x,ll c){    if (x<=0)        return;    for (;x<=m;x+=lowbit(x))        t[x]+=c;}inline ll query(int x){    ll res=0;    for (;x;x-=lowbit(x))        res+=t[x];    return res;}struct Node *null;struct Node{    Node *fa,*c[2];    int col;    int val;    ll sum;    inline void upd(){sum=c[0]->sum+c[1]->sum+val;}    inline bool getson(){return fa->c[0]!=this;}    inline void rotate(){        Node *y=fa,*z=y->fa;        if (y->col)            col=y->col,y->col=0;        else            z->c[y->getson()]=this;        int k=getson();        fa=z;        y->c[k]=c[k^1],c[k^1]->fa=y;        c[k^1]=y,y->fa=this;        sum=y->sum,y->upd();    }    void splay(){        for (;!col;rotate())            if (!fa->col)                getson()!=fa->getson()?rotate():fa->rotate();    }} d[N];inline void cover(Node *x,int c){    Node *y=null;    for (;x!=null;y=x,x=x->fa){        x->splay();        x->c[1]->col=x->col;        x->c[1]=y;        add(y->col,-y->sum),add(x->col,y->sum);        y->col=0;        x->upd();    }    add(y->col,-y->sum);    add(y->col=c,y->sum);}struct EDGE{    int to;    EDGE *las;} e[N*2];int ne;EDGE *last[N];int fa[N][17],dep[N];void init(int x){    dep[x]=dep[fa[x][0]]+1;    for (int i=1;1<
         
          
           las) if (ei->to!=fa[x][0]) fa[ei->to][0]=x,init(ei->to);}inline int LCA(int u,int v){ if (dep[u]
           
            >=1,++i) if (k&1) u=fa[u][i]; if (u==v) return u; for (int i=16;i>=0;--i) if (fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0];}struct Path{ int u,v;} p[N];struct Oper{ int l,r,num;} o[N];inline bool cmpo(const Oper &x,const Oper &y){return x.r
            
             splay(); anc->c[1]=null; anc->upd(); d[lca].col=anc->col; } else anc=d[lca].fa; d[lca].fa=null; cover(&d[u],i),cover(&d[v],i); d[lca].splay(); d[lca].fa=anc; for (;j<=Q && o[j].r<=i;++j) ans[o[j].num]=query(o[j].r)-query(o[j].l-1); } for (int i=1;i<=Q;++i) printf("%lld\n",ans[i]); return 0;}
            
           
          
        
       
      
     
    

---

总结

\(LCT\)真是太好打了……

看到类似于染色的题目，不要忘了\(LCT\)啊……