蒟蒻求助线段树合并

又MLE了。。

on test 67。

感觉没有地方可以优化了。

// 从未在意的名字永远不会被提起 雪葉/鹤见江野

/*
+
++
+++
++++
+++++
++++++
+++++++
++++++++
+++++++++
++++++++++
+++++++++++
++++++++++++
+++++++++++++
++++++++++++++
+++++++++++++++
++++++++++++++++
+++++++++++++++++
++++++++++++++++++
+ +++++++++++++++++
+  ++++++++++++++ ++
+   +++++++++++++  ++
+    ++++++++++++   ++
+     +++++++++++    ++
+      ++++++++++     ++
+       +++++++++      ++
+        ++++++++       ++
+         +++++++++++++++++
+          +++++++++++++++++
+           ++++++++++++++
+            +++++++++++
+             ++++++++
+              +++++
+               ++
+               +
+               +
+              ++
+             +++
+            ++++
+           +++++
+           +++++
+           +++++
+           +++++
+     +     +++++
+    +++    +++++
+   ++ ++   +++++
+  ++   ++  +++++
+ ++  +  ++ +++++
+++  +++  +++++++
++  ++ ++  ++++++

 ++++++++      +++++++++++     +++      +++        ++++++++        ++++++++
+++++++++     +++++++++++++    +++      +++       +++    +++      +++    +++
+++          +++   +++   +++   +++      +++      +++   ++++++    +++      +++
+++          +++   +++   +++   +++      +++      +++ +++  +++           +++
+++          +++   +++   +++   +++ ++   +++ ++   ++++++   +++         +++
+++++++++    +++   +++   +++   +++ ++   +++ ++    +++    +++        +++    ++
 ++++++++    +++   +++   +++   +++++    +++++      ++++++++       +++++++++++
*/
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <set>
#define nullptr NULL
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
#define rg(x) for(int i=1;i<=(x);i++){
#define rg_(i,x) for(int i=1;i<=(x);i++){
#define gr }
#define rrg(x) for(int i=0;i<(x);i++)
#define rdln(a) a[i]=read();
#define rdln0(a,x) rrg(x) rdln(a) gr
#define rdln1(a,x) rg(x) rdln(a) gr
//#define int long long
#define newe(n) struct Edge{int v,nxt;}e[n*2+5];\
typedef int arr[n+5];\
arr h;\
int cnt=1;\
inline void addedge(int u,int v){e[cnt]=(Edge){v,h[u]};h[u]=cnt++;}
#define mgs int fa[1<<22],sz[1<<22],t[1<<22];\
inline int f(int x){return x==fa[x]?x:fa[x]=f(fa[x]);}\
inline int u(int x,int y)\
{\
    int fx=f(x),fy=f(y);\
    if(fx==fy)return 0;\
    if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;\
    fa[fx]=fy,sz[fy]+=sz[fx];\
    return 1;\
}
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}
inline int re1d()
{
    char c=getchar();
    while(c<48||c>49)c=getchar();
    return c&1;
}
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
struct Node
{
    Node *lc,*rc;
    int maxn;
    Node(){lc=rc=NULL,maxn=0;}
    Node(int x):maxn(x){}
}*root[1000005];
inline int mx(Node* x)
{
    if(x==nullptr)return 0;
    return x->maxn;
}
inline void maintain(Node *&o,int l,int r)
{
    if(l==r)return;
    o->maxn=max(mx(o->lc),mx(o->rc));
}
Node* merge(Node *&a,Node *b,int l,int r)
{
    if(a==nullptr)return a=b;
    if(b==nullptr)return a;
    if(l==r)
    {
        a->maxn+=b->maxn;
        return a;
    }
    int m=l+r>>1;
    a->lc=merge(a->lc,b->lc,l,m);
    a->rc=merge(a->rc,b->rc,m+1,r);
    maintain(a,l,r);
    return a;
}
Node *nodes[50000005];
int ccc=0;
inline Node* newNode()
{
    return nodes[++ccc]=new Node();
}
void insert(Node *&o,int l,int r,int p,int v)
{
    if(o==nullptr)o=newNode();
    if(l==r)
    {
        o->maxn+=v;
        return;
    }
    int m=l+r>>1;
    if(p<=m)insert(o->lc,l,m,p,v);
    else insert(o->rc,m+1,r,p,v);
    maintain(o,l,r);
}
inline int query(Node *x,int l,int r)
{
    if(l==r)return r;
    int m=l+r>>1;
    if(mx(x->lc)>=mx(x->rc))return query(x->lc,l,m);
    else return query(x->rc,m+1,r);
}
//newe(1000005);
std::vector<int> G[1000005];
int pigstd=100000;
int dep[1000005],ans[1000005];
void dfs(int u,int fa_)
{
    dep[u]=dep[fa_]+1;
    for(auto v:G[u])if(v!=fa_)dfs(v,u);
}
void pigstd_AK_IOI(int u,int fa)
{
//  for(int i=h[u];i;i=e[i].nxt)
    for(auto v:G[u])
    {
//      int v=e[i].v;
        if(v==fa)continue;
        pigstd_AK_IOI(v,u);
        merge(root[u],root[v],1,pigstd);
    }
    ans[u]=query(root[u],1,pigstd)-dep[u];
}
signed main()
{
    int n=read();pigstd=n;
    rg(n-1)int x=read(),y=read();G[x].emplace_back(y);G[y].emplace_back(x);gr
    dfs(1,0);
    rg(n)insert(root[i],1,n,dep[i],1);gr
    pigstd_AK_IOI(1,0);
    rg(n)odl(ans[i]<0?0:ans[i]);gr
    rg(ccc)delete(nodes[i]);gr
    return 0;
}