线段树合并板子求调/kel
查看原帖
线段树合并板子求调/kel
177000
vicky2048_2楼主2024/1/24 12:01

rt

#include<bits/stdc++.h>
#define N 100005
#define T 80*N
#define L lc[no]
#define R rc[no]
using namespace std;
int n,m,sz[N],son[N],dep[N],fa[N],t[N],r[N],cnt,bh,fir[N],z[N],len,lsh[N],op[N],x[N],y[N];
struct E{ int nex,to;}e[N<<1];
struct tree{
    int lc[T],rc[T],tot[T],num[T];
    inline void ins(int &no,int l,int r,int pl,int k){
        if(pl>r||pl<l) return ;
        if(!no) no=++bh;
        tot[no]+=k;
        if(l==r){ num[no]=lsh[l]; return ;}
        int mi=l+r>>1;
        ins(L,l,mi,pl,k); ins(R,mi+1,r,pl,k);
        if(tot[L]>=tot[R])
            num[no]=num[L];
        else num[no]=num[R];
        tot[no]=tot[L]+tot[R];
    }
    inline void merge(int &no,int r2,int l,int r){
        if(!r2) return ;
        if(!no){ no=r2; return ;}
        if(l==r){ tot[no]+=tot[r2]; return ;}
        int mi=l+r>>1;
        merge(L,lc[r2],l,mi); merge(R,rc[r2],mi+1,r);
        if(tot[L]>=tot[R])
            num[no]=num[L];
        else num[no]=num[R];
        tot[no]=tot[L]+tot[R];
    }
}tr;
int lca(int,int);
void add(int,int),cf(int,int,int),dfs(int),dfs2(int,int),dfs3(int);
signed main(){
    scanf("%d%d",&n,&m); len=m;
    for(int i=1,a,b;i<n;++i){
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    dfs(1),dfs2(1,1);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
        lsh[i]=z[i];
    }
    sort(lsh+1,lsh+1+len);
    len=unique(lsh+1,lsh+1+len)-lsh-1;
    for(int i=1;i<=len;++i)
        op[lsh[i]]=i;
    for(int i=1;i<=m;++i)
        cf(x[i],y[i],op[z[i]]);
    dfs3(1);
    for(int i=1;i<=n;++i) printf("%d\n",tr.num[r[i]]);
    return 0;
}
void add(int a,int b){
    e[++cnt].nex=fir[a],e[cnt].to=b,fir[a]=cnt;
    e[++cnt].nex=fir[b],e[cnt].to=a,fir[b]=cnt;
}
void dfs(int no){
    ++sz[no];
    for(int i=fir[no];i;i=e[i].nex){
        int v=e[i].to;
        if(v==fa[no]) continue;
        dep[v]=dep[no]+1; fa[v]=no;
        dfs(v);
        sz[no]+=sz[v];
        if(sz[v]>sz[son[no]]) son[no]=v; 
    }
}
void dfs2(int no,int to){
    t[no]=to;
    if(!son[no]) return ;
    dfs2(son[no],to);
    for(int i=fir[no];i;i=e[i].nex){
        int v=e[i].to;
        if(v!=fa[no]&&v!=son[no])
            dfs2(v,v);
    }
}
int lca(int a,int b){
    while(t[a]!=t[b]){
        if(dep[t[a]]>dep[t[b]])
            a=fa[t[a]];
        else b=fa[t[b]];
    }
    return dep[a]>dep[b]?b:a;
}
void cf(int x,int y,int z){
    int lc=lca(x,y);
    tr.ins(r[x],1,len,z,1);
    tr.ins(r[y],1,len,z,1);
    tr.ins(r[lc],1,len,z,-1);
    if(fa[lc])
        tr.ins(r[fa[lc]],1,len,z,-1);
}
void dfs3(int no){
    for(int i=fir[no];i;i=e[i].nex){
        int v=e[i].to;
        if(v==fa[no]) continue;
        dfs3(v);
        tr.merge(r[no],r[v],1,len);
    }
    tr.merge(r[no],r[0],1,len);
}
2024/1/24 12:01
加载中...