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

线段树合并+树上差分。

模板题啊。

线段树合并和 Treap 合并还挺像的，就是从根节点开始将小的合并到大的上面去，然后合并的时候在大的上面做一下处理就好了。。。

这里写的是离线写法。。但这种写法是会破坏大线段树的结构的。。。

inline ll merge(ll l,ll r,ll x,ll y){
    if(!x||!y)  return x+y;
    if(l==r){
        tree[x].sm+=tree[y].sm;
        return x;
    }
    ll mid=(l+r)>>1;
    lc[x]=merge(l,mid,lc[x],lc[y]);
    rc[x]=merge(mid+1,r,rc[x],rc[y]);
    pushup(x);
    return x;
}//核心代码

inline void solve(ll x,ll fat){
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==fat)   continue;
        solve(to,x);
        rt[x]=merge(1,maxn,rt[x],rt[to]);
    }
    ans[x]=(!tree[rt[x]].sm?0:tree[rt[x]].id);
}

还有一种在线写法只是很耗空间。。。每一次新开一个节点。。。

把离线的 \(x\) 改为 \(root\) ，然后每一次合并操作在 \(tree[root]\) 上操作就行了。。。

代码不放了。

至于每个节点建一颗线段树。。。和主席树很像。。。每一次保存一个点 \(x\) 所拥有的线段树最上面的那个点记作 \(rt[x]\) ，虽然最后都是在 \(tree\) 数组上进行操作的但是很明显 \(rt\) 与 \(rt\) 之间并没有直接关系（也没有边连接

不能之间传 \(l\) ，\(r\) 的参了，要开 \(lc\) 和 \(rc\) 数组。。。

呃，没了。

#include <bits/stdc++.h>
#define ll long long
#define maxn 2000001
using namespace std;
ll n,m,u,v,w;
ll hd[maxn],cnt;
ll rt[maxn<<2],tot;
ll lc[maxn<<2],rc[maxn<<2];
ll ans[maxn<<2];
ll fa[maxn],top[maxn];
ll dep[maxn],val[maxn],son[maxn];
struct Node{
    ll nx,to;
}e[maxn<<1];
struct NoDe{
    ll sm=0,id=0;
}tree[maxn<<2];

inline ll read(){
    ll x=0,f=0;char c=getchar();
    while(!isdigit(c))  f|=c=='-',c=getchar();
    while(isdigit(c))   x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return f?-x:x;
}

inline void add(ll u,ll v){
    e[++cnt].to=v;
    e[cnt].nx=hd[u];
    hd[u]=cnt;
}

inline void dfs1(ll x){
    dep[x]=dep[fa[x]]+1;
    val[x]=1;
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==fa[x])   continue;
        fa[to]=x;
        dfs1(to);
        val[x]+=val[to];
        if(val[son[x]]<val[to]||!son[x])
            son[x]=to;
    }
}

inline void dfs2(ll x,ll tp){
    top[x]=tp;
    if(son[x])  dfs2(son[x],tp);
    for(register int i=hd[x];i;i=e[i].nx)   
        if(e[i].to!=fa[x]&&e[i].to!=son[x])
            dfs2(e[i].to,e[i].to);
}

inline ll LCA(ll x,ll y){
    for(;top[x]!=top[y];dep[top[x]]<dep[top[y]]?y=fa[top[y]]:x=fa[top[x]]);
    return dep[x]<dep[y]?x:y;
}

inline void pushup(ll f){
    if(!lc[f]){
        tree[f].sm=tree[rc[f]].sm;
        tree[f].id=tree[rc[f]].id;
        return;
    }
    if(!rc[f]){
        tree[f].sm=tree[lc[f]].sm;
        tree[f].id=tree[lc[f]].id;
        return;
    }
    if(tree[lc[f]].sm>=tree[rc[f]].sm){
        tree[f].sm=tree[lc[f]].sm;
        tree[f].id=tree[lc[f]].id;
    }
    else{
        tree[f].sm=tree[rc[f]].sm;
        tree[f].id=tree[rc[f]].id;
    }
}

inline void update(ll l,ll r,ll &f,ll x,ll y){
    if(!f)  f=++tot;
    if(l==r){
        tree[f].sm+=y;
        tree[f].id=x;
        return;
    }
    ll mid=(l+r)>>1;
    if(x<=mid)      update(l,mid,lc[f],x,y);
    else            update(mid+1,r,rc[f],x,y);
    pushup(f);
}

inline ll merge(ll l,ll r,ll x,ll y){
    if(!x||!y)  return x+y;
    if(l==r){
        tree[x].sm+=tree[y].sm;
        return x;
    }
    ll mid=(l+r)>>1;
    lc[x]=merge(l,mid,lc[x],lc[y]);
    rc[x]=merge(mid+1,r,rc[x],rc[y]);
    pushup(x);
    return x;
}

inline void solve(ll x,ll fat){
    for(register int i=hd[x];i;i=e[i].nx){
        ll to=e[i].to;
        if(to==fat)   continue;
        solve(to,x);
        rt[x]=merge(1,maxn,rt[x],rt[to]);
    }
    ans[x]=(!tree[rt[x]].sm?0:tree[rt[x]].id);
}

int main(){
    n=read();m=read();
    for(register int i=1;i<n;++i){
        u=read();v=read();
        add(u,v);
        add(v,u);
    }
    dfs1(1);
    dfs2(1,1);
    for(register int i=1;i<=m;++i){
        u=read();v=read();w=read();
        ll lca=LCA(u,v);
        update(1,maxn,rt[u],w,1);
        update(1,maxn,rt[v],w,1);
        update(1,maxn,rt[lca],w,-1);
        update(1,maxn,rt[fa[lca]],w,-1);
    }
    solve(1,0);
    for(register int i=1;i<=n;++i)
        printf("%lld\n",ans[i]);
    return 0;
}