模拟赛题不方便公开。就是普通的全局平衡二叉树建树

NOIlinux 和 UOJ 上“这里”使用现在的写法会使得 t[2].fa = 2，但换成 t[rs(u)=bld(l,i-1)].fa = u, t[ls(u)=bld(i+1,r)].fa = u; 就对了
CF 上两种写法都能过

查不出 UB/RE，求教啥情况啊 /kk

#include <bits/stdc++.h>
using namespace std;
#define For(i,x,y,...) for(int i=x,##__VA_ARGS__;i<=(y);++i)
#define Rep(i,x,y,...) for(int i=x,##__VA_ARGS__;i<(y);++i)
#define pb emplace_back
typedef vector<int> Vi;

const int N = 1e6+5;
int n;

    int fa[N],dep[N],siz[N],son[N],top[N],id[N];
    Vi e[N];
    #define ls(u) t[u].ch[0]
    #define rs(u) t[u].ch[1]
    struct { int ch[2],fa; } t[N];
    int bld(int l,int r) {
        if( l > r ) return 0;
        auto w=[&](int u) { return siz[u]-siz[son[u]]; };
        int s=0; For(i,l,r) s += w(id[i]);
        For(i,l,r, x = 0) {
            x += w(id[i]);
            if( x+x >= s ) {
                int u = id[i];
                t[rs(u)=bld(l,i-1)].fa = t[ls(u)=bld(i+1,r)].fa = u; // 这里
                return u;
            }
        }
        assert(0);
    }
    #undef ls
    #undef rs
    void dfs1(int u) {
        dep[u] = dep[fa[u]]+1, siz[u] = 1;
        for(int v : e[u]) {
            fa[v] = u, dfs1(v), siz[u] += siz[v];
            if( siz[v] > siz[son[u]] ) son[u] = v;
        }
    }
    void dfs2(int u,int t) {
        top[u] = t;
        if( !son[u] ) {
            int ind=0; for(int i = u; top[i] == t; i = fa[i]) id[++ind] = i;
            bld(1,ind);
        } else dfs2(son[u],t);
        for(int v : e[u]) if( v != son[u] ) dfs2(v,v);
    }

signed main() { freopen("in","r",stdin); freopen("elixir.out","w",stdout);
    cin>>n; Rep(i,1,n, x,y) cin>>x>>y, e[x].pb(y);
    dfs1(1), dfs2(1,1);
    For(i,1,n) cout<<t[i].fa<<' ';
    return 0;
}
/*
in:
7
1 2
1 7
2 3
3 4
4 5
5 6
out:
3 1 0 5 3 5 0 
*/

upd 1

不知道是不是数据小，t[ls(u)=bld(i+1,r)].fa = t[rs(u)=bld(l,i-1)].fa = u; 也能过