关于线段树合并

mxqz/kel

MLE ON #131

节点回收也写了 还是挂了/kk

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define dec(x) fixed<<setprecision(x)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

template<class T> inline void rd(T &x){
    int fl=1;x=0;char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
    x*=fl;
}
template<class T> inline void wr(T x){
    if(x<0) x=-x,putchar('-');
    if(x<10){putchar(x+'0');return ;}
    int tmp[30]={0},cnt=0;
    while(x) tmp[cnt++]=x%10,x/=10;
    for(re i=cnt-1;i>=0;--i) putchar(tmp[i]+'0');
}

// ---------- IO ---------- //

const int N=1e6+5,M=1.919810e7+5;
int n,hd[N],tot,cnt,Ans[N];
struct edge{int nxt,t;}es[N<<1];
inline void add(int x,int y){es[++tot]=(edge){hd[x],y};hd[x]=tot;}

struct SGT{
    #define mid ((l+r)>>1)
    int rt[N],L[M],R[M],ans[M],id[M],st[M],tp=0;
    inline int newnode(){if(tp) return st[tp--];return ++cnt;}
    inline void del(int x){L[x]=R[x]=ans[x]=id[x]=0;st[++tp]=x;}
    inline void pushup(int x){
        if(ans[L[x]]>=ans[R[x]]) ans[x]=ans[L[x]],id[x]=id[L[x]];
        else ans[x]=ans[R[x]],id[x]=id[R[x]];
    }
    inline int modify(int nw,int l,int r,int k){
        if(!nw) nw=newnode();
        if(l==r){++ans[nw];id[nw]=k;return nw;}
        if(k<=mid) L[nw]=modify(L[nw],l,mid,k);
        else R[nw]=modify(R[nw],mid+1,r,k);
        pushup(nw);return nw;
    }
    inline int merge(int a,int b,int l,int r){
        if(!a||!b) return (a|b);
        if(l==r){ans[a]+=ans[b];id[a]=l;del(b);return a;}
        L[a]=merge(L[a],L[b],l,mid),R[a]=merge(R[a],R[b],mid+1,r);
        pushup(a);del(b);return a;
    }
}T;

inline void dfs(int x,int fa,int dep){
    for(re i=hd[x];i;i=es[i].nxt)
        if(es[i].t!=fa) dfs(es[i].t,x,dep+1),T.rt[x]=T.merge(T.rt[x],T.rt[es[i].t],1,n);
    T.rt[x]=T.modify(T.rt[x],1,n,dep);Ans[x]=T.id[T.rt[x]]-dep;
}

// ----------  ---------- //

int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(re i=1;i<n;++i){int u,v;cin>>u>>v;add(u,v);add(v,u);}
    dfs(1,0,1);
    for(re i=1;i<=n;++i) cout<<Ans[i]<<"\n";
    return 0;
}

// ---------- Main ---------- //