线段树合并

Iceturky · 2024-07-01 21:30:27 · 个人记录

其实是简单东西。

代码上唯一需要注意的点反而来自动态开点。

尽量不要把区间范围放进结构体，可能会爆空间。

模板的代码

code

const int N=1e5+5,limit=1e5;

struct edge{
    int v,nxt;
}e[N<<1];
int head[N],tott;
void add(int u,int v){e[++tott]={v,head[u]},head[u]=tott;}

struct Seg_Tree{
    struct hhh{
        int s[2];
        int mx,c;
    }t[N<<5];
    int idx;
    void pushup(int x){
        if(t[t[x].s[0]].mx>=t[t[x].s[1]].mx)
            t[x].mx=t[t[x].s[0]].mx,t[x].c=t[t[x].s[0]].c;
        else
            t[x].mx=t[t[x].s[1]].mx,t[x].c=t[t[x].s[1]].c;
    }
    void update(int x,int l,int r,int c,int a){
        if(l==r)
            t[x].mx+=a,t[x].c=c;
        else{
            if(c<=mid){
                if(!t[x].s[0])
                    t[x].s[0]=++idx;
                update(t[x].s[0],l,mid,c,a);
            }else{
                if(!t[x].s[1])
                    t[x].s[1]=++idx;
                update(t[x].s[1],mid+1,r,c,a);
            }
            pushup(x);
        }
    }
    int merge(int x,int y,int l,int r){
        if(!x||!y) return x+y;
        if(l==r){
            t[x].mx=t[x].mx+t[y].mx;
            return x;
        }
        t[x].s[0]=merge(t[x].s[0],t[y].s[0],l,mid);
        t[x].s[1]=merge(t[x].s[1],t[y].s[1],mid+1,r);
        pushup(x);
        return x;
    }
}T;

int fa[21][N],dep[N];
void dfs(int u,int faa){
    fa[0][u]=faa;
    dep[u]=dep[faa]+1;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==faa)
            continue;
        dfs(v,u);
    }
}
void init(int n){
    for(int k=1;k<=19;k++)
        for(int i=1;i<=n;i++)
            fa[k][i]=fa[k-1][fa[k-1][i]];
}
int lca(int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=19;i>=0;i--)
        if(dep[fa[i][x]]>=dep[y])
            x=fa[i][x];
    if(x==y)
        return x;
    for(int i=19;i>=0;i--)
        if(fa[i][x]!=fa[i][y])
            x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}

void dfs_merge(int u,int faa){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v==faa)
            continue;
        dfs_merge(v,u);
        T.merge(u,v,1,limit);
    }
}

signed main(){
    int n=read(),q=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        add(u,v),add(v,u);
    }
    dfs(1,0);
    init(n);
    T.idx=n;
    while(q--){
        int u=read(),v=read(),x=read();
        T.update(u,1,limit,x,1);
        T.update(v,1,limit,x,1);
        int l=lca(u,v);
        T.update(l,1,limit,x,-1);
        if(fa[0][l])
            T.update(fa[0][l],1,limit,x,-1);
    }
    dfs_merge(1,0);
    for(int i=1;i<=n;i++)
        print(T.t[i].mx==0?0:T.t[i].c),pc('\n');
    return 0;
}