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

xingke233 / 2024-11-09 / 原文

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

涉及

  1. 树上差分
  2. 树剖求LCA
  3. 线段树动态开点
  4. 线段树合并
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL int
#define id(p) tree[p].id
#define ls(p) tree[p].ls
#define rs(p) tree[p].rs
#define ma(p) tree[p].ma
const int N=200005,M=300005;

LL n,m,k,u,v,w,x,y,z,ans[N];
LL head[M],net[M],val[M],idx;
LL d[N],siz[N],f[N],son[N],tp[N],id[N],rks[N],cnt;
LL root[N],tot;

struct node{
    LL id,ls,rs,ma;
}tree[N*40];

LL read(){
    LL s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return w*s;
}

void add(LL x,LL y){
    val[++idx]=y;
    net[idx]=head[x];
    head[x]=idx;
    return ;
}

void dfs1(LL x,LL fa){
    f[x]=fa,d[x]=d[fa]+1,siz[x]=1;
    for(int i=head[x];i;i=net[i]){
        LL v=val[i];
        if(v==fa) continue;
        dfs1(v,x);
        siz[x]+=siz[v];
        if(siz[son[x]]<siz[v]) son[x]=v;
    }
    return ;
}

void dfs2(LL x,LL top){
    tp[x]=top,id[x]=++cnt;
    rks[cnt]=x;
    if(son[x]){dfs2(son[x],top);}
    for(int i=head[x];i;i=net[i]){
        LL v=val[i];
        if(v==son[x]||v==f[x]) continue;
        dfs2(v,v);
    }
    return ;
}

LL lca(LL x,LL y){
    while(tp[x]!=tp[y]){
        if(d[tp[x]]<d[tp[y]]) swap(x,y);
        x=f[tp[x]];
    }
    if(id[x]>id[y]) swap(x,y);
    return x;
}

LL build(){
    tot++;
    ls(tot)=rs(tot)=ma(tot)=0;
    id(tot)=1e9;
    return tot;
}

void insert(LL x,LL p,LL l,LL r,LL val,LL z){
    if(l==r){
        ma(p)+=z;
        id(p)=val;
        return ;
    }
    LL mid=(l+r)>>1;
    if(val<=mid) {
        if(!ls(p)) ls(p)=build();
        insert(x,ls(p),l,mid,val,z);
    }
    else{
        if(!rs(p)) rs(p)=build();
        insert(x,rs(p),mid+1,r,val,z);
    }
    if(ma(ls(p))>ma(rs(p))){
        ma(p)=ma(ls(p));
        id(p)=id(ls(p));
    }else{
        if(ma(ls(p))==ma(rs(p))){
            id(p)=min(id(ls(p)),id(rs(p)));
            ma(p)=ma(ls(p));
        }else{
            ma(p)=ma(rs(p));
            id(p)=id(rs(p));
        }
    }
    return ;
}

LL merge(LL p,LL q,LL l,LL r){
    if(!p) return q;
    if(!q) return p;
    if(l==r){
        ma(p)+=ma(q);
        id(p)=l;
        return p;
    }
    LL mid=(l+r)>>1;
    ls(p)=merge(ls(p),ls(q),l,mid);
    rs(p)=merge(rs(p),rs(q),mid+1,r);
     if(ma(ls(p))>ma(rs(p))){
        ma(p)=ma(ls(p));
        id(p)=id(ls(p));
    }else{
        if(ma(ls(p))==ma(rs(p))){
            id(p)=min(id(ls(p)),id(rs(p)));
            ma(p)=ma(ls(p));
        }else{
            ma(p)=ma(rs(p));
            id(p)=id(rs(p));
        }
    }
    return p;
}

void dfs(LL p){
    if(siz[p]==1){
        ans[p]=id(root[p]);
        return ;
    }
    for(int i=head[p];i;i=net[i]){
        LL v=val[i];
        if(v==f[p]) continue;
        dfs(v);
        root[p]=merge(root[p],root[v],1,1e5);
    }
    ans[p]=id(root[p]);
    return ;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<n;i++){
        x=read(),y=read();
        add(x,y);add(y,x);
        root[i]=build();
    }
    root[n]=build();
    dfs1(1,1);
    dfs2(1,1);
    for(int i=1;i<=m;i++){
        x=read(),y=read(),z=read();
        LL la=lca(x,y);
        insert(x,root[x],1,1e5,z,1);
        insert(y,root[y],1,1e5,z,1);
        insert(la,root[la],1,1e5,z,-1);
        if(la!=f[la])
        insert(f[la],root[f[la]],1,1e5,z,-1);
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        printf("%d\n",ans[i]!=1e9?ans[i]:0);
    }
    return 0;
}