线段树合并 WA on #4 求助

WA on #4

#include <iostream>
#include <vector>
#define int long long
#define mid (l + r >> 1)
using namespace std;
inline int read()
{
    int ans = 0, f = 0;
    char c = getchar();
    while (!isdigit(c))
        f |= (c == '-'), c = getchar();
    while (isdigit(c))
        ans = (ans << 3) + (ans << 1) + c - 48, c = getchar();
    return f ? -ans : ans;
}
void write(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(48 + x % 10);
}
constexpr int N = 2e6 + 5;
constexpr int V = 2e6;
vector<int> g[N];
int cnt, root[N];
int top, recycle[N];
int n, d[N], ans[N];
struct tree
{
    int l, r, mx;
} t[N << 3];
inline int _new()
{
    if (top)
        return recycle[top--];
    return ++cnt;
}
inline void _delete(int p)
{
    t[p].l = t[p].r = t[p].mx = 0;
    recycle[++top] = p;
}
int add(int l, int r, int x, int p, int w)
{
    if (!p)
        p = _new();
    if (l == r)
    {
        t[p].mx += w;
        return p;
    }
    if (mid >= x)
        t[p].l = add(1, mid, x, t[p].l, w);
    if (mid < x)
        t[p].r = add(mid + 1, r, x, t[p].r, w);
    t[p].mx = max(t[t[p].l].mx, t[t[p].r].mx);
    return p;
}
int max(int l, int r, int p)
{
    if (l == r)
        return l;
    if (t[t[p].l].mx >= t[t[p].r].mx)
        return max(l, mid, t[p].l);
    return max(mid + 1, r, t[p].r);
}
int merge(int l, int r, int p1, int p2)
{
    if (!p1 || !p2)
        return p1 | p2;
    if (l == r)
    {
        t[p1].mx += t[p2].mx;
        _delete(p2);
        return p1;
    }
    t[p1].l = merge(l, mid, t[p1].l, t[p2].l);
    t[p1].r = merge(mid + 1, r, t[p1].r, t[p2].r);
    t[p1].mx = max(t[t[p1].l].mx, t[t[p1].r].mx);
    _delete(p2);
    return p1;
}
void dfs_merge(int u, int fa)
{
    d[u] = d[fa] + 1;
    for (int l = 0; l < g[u].size(); ++l)
    {
        int i = g[u][l];
        if (i != fa)
        {
            dfs_merge(i, u);
            root[u] = merge(1, V, root[u], root[i]);
        }
    }
    root[u] = add(1, V, d[u], root[u], 1);
    ans[u] = max(1, V, root[u]) - d[u];
}
signed main()
{
    n = read();
    for (int i = 1; i < n; ++i)
    {
        int u = read(), v = read();
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs_merge(1, 0);
    for (int i = 1; i <= n; ++i)
        write(ans[i]), putchar('\n');
    return 0;
}