P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并题解

· · 题解

UPD：对代码中的注释进行了一定的修改。

本文所说线段树均指权值线段树。

前置知识

讲差分是一定要先讲前缀和的。树上前缀和有两种，一种是从根节点到当前节点的路径权值和，一种是这个节点的子树和。这里我们只关心后一种前缀和。

容易发现只要从下往上，将每个节点的所有儿子合并再与它自己合并就可以求出树上前缀和。

由此可以启发出树上差分的方法。

假设我们要让点 i 到点 j 的路径上所有的点权加上 x，那么只需要让点 i,j 的权值加上 x，让 lca_{i,j} 的权值减去 x，同时让 lca_{i,j} 的父节点（如果存在）减去 x 即可。读者可以结合上文所讲树上前缀和，自己去思考一下这样的正确性。

线段树合并

一般情况

先不考虑树上，先来考虑普通的两棵线段树如何合并。

将两棵线段树合并，那么其实就是建一棵新的线段树，将两棵线段树维护的信息合并在新树上。权值线段树维护的是桶，将两个桶对应下标的值相加即为合并。

那么显然，对于叶子节点，将其维护的值相加即可。对于非叶子节点，直接 push_up 即可。具体实现就是一个 dfs 的过程，非常简单。

实际为了节约空间复杂度，往往选择将一棵线段树合并到另一棵上。

设树的大小为 n，这么做的时间复杂度是稳定 O(n\log n) 的。这显然不是我们想要的复杂度。

这时就要用到权值线段树的一个重要技巧：动态开点。这样可以最大化节约内存。如果合并时，遇到其中一个线段树的当前节点为空，那么直接将另一个节点作为新线段树对应位置的儿子即可。即共用这个儿子。

复杂度分析

将两个线段树合并时，遇到空节点直接返回，也就是只有两个线段树的重合部分会被 dfs 到。所以总的合并次数不会超过较小的线段树的节点数。即单次合并复杂度不会超过 O(n\log n)。

如果进行了很多次合并，那么时间复杂度依然是 O(n\log n)，原因是如果将两个线段树合并，事实上不会增加新的节点，而较小的线段树永远的消失了，也就是对于每一棵线段树，在合并一次后，要么对方消失，要么自己消失。即所有的节点都只会被合并一次。那么无论合并多少次，总的时间复杂度就是 O(n\log n)。

这一部分参考了这一篇题解。

由上面的分析也可知空间复杂度为 O(n\log n)。但是常数较大。对于本题，由于利用树上差分修改，每次需要修改至多四个节点，空间复杂度有四倍的常数。

树上合并

和一般情况其实并没有什么区别。用树上前缀和的思想，将一个节点所有儿子对应的线段树合并，然后再和它自身合并即可。

本题解法

对于每一个节点，开一颗权值线段树，维护值域最大值。修改时利用树上差分进行修改。然后进行树上前缀和合并即可。

时空复杂度 O(n\log n)，注意空间有四倍的常数。

代码

代码有较为详细的注释。

#include<bits/stdc++.h>
#define ll int
#define dd double
#define lson c[id].ls
#define rson c[id].rs
#define mid ((l+r)/2)
using namespace std;
inline ll read(){

    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        write(x/10);
    }
    putchar(x%10+'0');
}
const ll N=1e5+9,R=1e5;
ll n,m;
ll ccnt;//动态开点计数器
struct NODE{
    ll ls,rs,sum,lei;//左右儿子，最大值的大小和种类 
}c[N*80];//权值树 
//由于对于每次修改，根据树上差分的思想，只需要修改四个点，由于动态开点
//至多只需要新开4*logn个点，合并是可以共用节点
//所以空间复杂度o(n*4*logn) 
ll root[N*80];//以i号节点为根的权值树的根节点编号 
ll deep[N],fa[N][20];//lca
//链式前向星
ll h[N*2],bcnt;
struct LIAN{
    ll to,ne;
}b[N*2];
ll ans[N];
inline void addb(ll u,ll v){

    b[++bcnt].ne=h[u];
    b[bcnt].to=v;
    h[u]=bcnt;
}
//lca
void init(ll now,ll father){
    fa[now][0]=father;
    deep[now]=deep[father]+1;
    for(int i=1;i<=19;i++){
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(ll i=h[now];i;i=b[i].ne){
        if(b[i].to==father){
            continue;
        }
        init(b[i].to,now);
    }
    return;
}
ll lca(ll u,ll v){
    if(deep[u]!=deep[v]){
        if(deep[u]<deep[v]){
            swap(u,v);
        }
        for(int i=19;i>=0;i--){
            if(deep[fa[u][i]]>=deep[v]){
                u=fa[u][i];
            }
        }
    }
    if(u==v){
        return u;
    }
    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
//权值线段树
void pu(ll id){//push_up
    if(lson==0){
        c[id].sum=c[rson].sum;
        c[id].lei=c[rson].lei;
        return;
    }
    if(rson==0){
        c[id].sum=c[lson].sum;
        c[id].lei=c[lson].lei;
        return;
    }
    if(c[lson].sum>=c[rson].sum ){
        c[id].sum =c[lson].sum ;
        c[id].lei =c[lson].lei ;
    }
    if(c[lson].sum <c[rson].sum ){
        c[id].sum =c[rson].sum ;
        c[id].lei =c[rson].lei ;
    }
}
void change(ll &id,ll l,ll r,ll v,ll val){
    if(!id){
        id=++ccnt;
    }
    if(l==r){
        c[id].sum +=val;//l==r时，此区间只有一种救济粮，可以直接相加 
        c[id].lei =v;
        return;
    }
    if(v<=mid){
        change(lson,l,mid,v,val);
    }
    else{
        change(rson,mid+1,r,v,val);
    }
    pu(id);
}
ll merge(ll u,ll v,ll l,ll r){//将子线段树v合并到子线段树u上
    if(u==0||v==0){
        return u+v;
    }
    if(l==r){
        c[u].sum +=c[v].sum ;
        c[u].lei=l;
        return u;
    } 
    c[u].ls =merge(c[u].ls ,c[v].ls ,l,mid);
  //关于这里为什么要给c[u].ls赋值：
  //当u.ls等0而v.ls不等0时，为减少复杂度，让u.ls共用v.ls这个节点。
    c[u].rs =merge(c[u].rs ,c[v].rs ,mid+1,r);//同上
    pu(u); 
    return u; 
}
void cacl(ll id,ll fa){//统计答案 
    for(int i=h[id];i;i=b[i].ne ){
        ll u=b[i].to ;
        if(u==fa)continue;
        cacl(u,id);
        root[id]=merge(root[id],root[u],1,R);
    //这里与上文同理
    }
    if(c[root[id]].sum ==0){
        ans[id]=0;
    }
    else{
        ans[id]=c[root[id]].lei ;
    }
}
int main(){
//  freopen("P4556_15.in","r",stdin);
    n=read();
    m=read();
    for(int i=1;i<n;i++){

        ll a=read(),b=read();
        addb(a,b);
        addb(b,a);
    } 

    init(1,0);
    for(int i=1;i<=m;i++){
        ll x=read(),y=read(),z=read();
        change(root[x],1,R,z,1);
        change(root[y],1,R,z,1);
        change(root[lca(x,y)],1,R,z,-1);
        change(root[fa[lca(x,y)][0]],1,R,z,-1);//树上差分 
    }
    cacl(1,0);
    for(int i=1;i<=n;i++){
        write(ans[i]);
        putchar('\n');
    }
    return 0;
}