求助线段树合并 TLE On #67

//#pragma GCC optimize(3)
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse")
//#pragma GCC optimize("-fgcse-lm")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-ftree-pre")
//#pragma GCC optimize("-ftree-vrp")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-falign-jumps")
//#pragma GCC optimize("-falign-loops")
//#pragma GCC optimize("-falign-labels")
//#pragma GCC optimize("-fdevirtualize")
//#pragma GCC optimize("-fcaller-saves")
//#pragma GCC optimize("-fcrossjumping")
//#pragma GCC optimize("-fthread-jumps")
//#pragma GCC optimize("-funroll-loops")
//#pragma GCC optimize("-fwhole-program")
//#pragma GCC optimize("-freorder-blocks")
//#pragma GCC optimize("-fschedule-insns")
//#pragma GCC optimize("inline-functions")
//#pragma GCC optimize("-ftree-tail-merge")
//#pragma GCC optimize("-fschedule-insns2")
//#pragma GCC optimize("-fstrict-aliasing")
//#pragma GCC optimize("-fstrict-overflow")
//#pragma GCC optimize("-falign-functions")
//#pragma GCC optimize("-fcse-skip-blocks")
//#pragma GCC optimize("-fcse-follow-jumps")
//#pragma GCC optimize("-fsched-interblock")
//#pragma GCC optimize("-fpartial-inlining")
//#pragma GCC optimize("no-stack-protector")
//#pragma GCC optimize("-freorder-functions")
//#pragma GCC optimize("-findirect-inlining")
//#pragma GCC optimize("-fhoist-adjacent-loads")
//#pragma GCC optimize("-frerun-cse-after-loop")
//#pragma GCC optimize("inline-small-functions")
//#pragma GCC optimize("-finline-small-functions")
//#pragma GCC optimize("-ftree-switch-conversion")
//#pragma GCC optimize("-foptimize-sibling-calls")
//#pragma GCC optimize("-fexpensive-optimizations")
//#pragma GCC optimize("-funsafe-loop-optimizations")
//#pragma GCC optimize("inline-functions-called-once")
//#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<ctime>
#include<cmath>
#include<cctype>
#include<bitset>
#include<vector>
#include<cstdio>
#include<random>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define INF 1e9
#define LLINF 1e18
#define ll long long
#define N 1000005
using namespace std;
int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void print(int x){
    if(x<0) putchar('-'),x=~(x-1);
    if(x>9) print(x/10);
    putchar(x%10+48);
}
int n,head[N],tot,cnt,rt[N],ans[N],deep[N];
struct Segment{
    int ls,rs;
    int Max,p;
}node[N*20];
struct Edge{
    int to,nxt;
}e[N<<1];
void add_edge(int x,int y){
    e[++tot].to=y;
    e[tot].nxt=head[x];
    head[x]=tot;
}
void getnew(int index){
    if(node[node[index].ls].Max>=node[node[index].rs].Max){
        node[index].Max=node[node[index].ls].Max;
        node[index].p=node[node[index].ls].p;
    }
    else{
        node[index].Max=node[node[index].rs].Max;
        node[index].p=node[node[index].rs].p;
    }
}
void insert(int &index,int l,int r,int k){
    if(!index) index=++cnt;
    if(l==r){
        ++node[index].Max;
        node[index].p=l;
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid) insert(node[index].ls,l,mid,k);
    else insert(node[index].rs,mid+1,r,k);
    getnew(index);
}
int merge(int ls,int rs,int l,int r){
    if(!ls || !rs) return ls+rs;
    if(l==r){
        node[ls].Max+=node[rs].Max;
        node[ls].p=l;
        return ls;
    }
    int mid=(l+r)>>1;
    node[ls].ls=merge(node[ls].ls,node[rs].ls,l,mid);
    node[ls].rs=merge(node[ls].rs,node[rs].rs,mid+1,r);
    getnew(ls);return ls;
}
void dfs(int x,int f){
    deep[x]=deep[f]+1;
    insert(rt[x],1,n,deep[x]);
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==f) continue;
        dfs(y,x);
        rt[x]=merge(rt[x],rt[y],1,n);
    }
    ans[x]=node[rt[x]].p-deep[x];
}
int main(){
    n=read();
    for(int i=1;i<n;++i){
        int x=read(),y=read();
        add_edge(x,y);
        add_edge(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

开了火车头也没卡过去 /kk