求助长链剖分，谢谢

RT, Wa on Test3 Line 1

思路：用 vector 存储每一条节点所在长链的信息，倒序存储，即 vector 最后一个元素表示与 u 距离为 0 的节点个数，倒数第二个表示与 u 距离为 1 的节点个数，依次类推

#include<bits/stdc++.h>
#define int long long
#define cint const int&
using namespace std;

const int maxn = 1e6 + 10;
vector<int>* d[maxn];
int ans[maxn], dep[maxn], son[maxn], cnt, head[maxn];
struct {
    int nxt, v;
}edge[maxn << 1];
inline void addedge(cint u, cint v) {
    edge[++cnt] = { .nxt = head[u],.v = v };
    head[u] = cnt;
}

void dfs(cint u, cint fa) {
    int maxdep = 0;
    dep[u] = dep[fa] + 1;
    for (auto i = head[u]; i; i = edge[i].nxt) {
        const auto v = edge[i].v;
        if (v == fa) continue;
        dfs(v, u);
        if (dep[v] > maxdep) maxdep = dep[son[u] = v];
    }
    if (!maxdep) { 
        ans[u] = 0; 
        d[u] = new vector<int>{ 1 };
        return; 
    }
    d[u] = d[son[u]];
    (*d[u]).push_back(1);
    auto utp = (*d[u]).size() - 2;
    for (auto i = head[u]; i; i = edge[i].nxt) {
        const auto v = edge[i].v;
        if (v == fa || v == son[u]) continue;
        int mtp = utp, ytp = (*d[v]).size() - 1;
        while (ytp >= 0) {
            (*d[u])[mtp] += (*d[v])[ytp];
            --mtp; --ytp;
        }
        delete d[v];
    }
    int maxd = 0;
    for (int i = utp + 1; i >= 0; --i) {
        if ((*d[u])[i] > maxd) {
            maxd = (*d[u])[i];
            ans[u] = utp - i + 1;
        }
    }
}
int n;

signed main() {
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        addedge(u, v), addedge(v, u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << '\n';
}