题目大意：给定一棵 $N$ 个节点的无根树（通常默认 $1$ 为根），对于每个节点 $u$，找到一个相对深度 $d$，使得在 $u$ 的子树中，到 $u$ 距离为 $d$ 的节点数量最多。如果有多个 $d$ 满足条件，取最小的 $d$。

我们可以定义状态 $f[u][i]$ 表示：在以 $u$ 为根的子树中，距离 $u$ 深度为 $i$ 的节点个数。

转移方程非常简单：

同时 $f[u][0] = 1$（节点本身）。

每次计算完 $f[u]$ 的所有元素后，我们只需要遍历一遍 $f[u]$ 数组，找出最大值对应的最小下标 $d$ 即可。

vector<int> tr[N];
int f[N][N]; // f[u][j] 表示以 u 为根的子树中，相对深度为 j 的节点数
int ans[N];

void dfs(int u, int fa) {
    f[u][0] = 1;
    ans[u] = 0;
    for (int v : tr[u]) {
        if (v == fa) continue;
        dfs(v, u);
        for (int j = 1; j <= n; j++) {
            f[u][j] += f[v][j - 1];
        }
        int maxv = 1;
        for (int j = 1; j <= n; j++) {
            if (f[u][j] > maxv) {
                maxv = f[u][j];
                ans[u] = j;
            }
        }
    }
}

瓶颈：状态有两维，空间复杂度和时间复杂度都是 $O(N^2)$，对于 $N = 10^6$ 的数据量来说，肯定会 MLE 和 TLE。

核心优化原理：长链剖分

如果仔细观察转移方程：$f[u][i] = f[v][i-1]$，你会发现 $v$ 的信息其实可以直接“平移”给 $u$。这就引出了长链剖分的核心思想：把最长的子树路径直接继承，其余短分支再暴力合并。

和重链剖分（根据子树节点数量划分重儿子）不同，长链剖分是根据子树的深度来划分重儿子的。对于每个节点 $u$，我们把它所有儿子中，子树深度最深

的那个儿子称为“重儿子（长儿子）”，其余的称为“轻儿子”。

内存复用技术（空间和时间双重优化）

因为重儿子的深度是最深的，我们可以让节点 $u$ 直接继承重儿子 $v$ 的 $f$ 数组。具体怎么继承呢？利用指针！

让 $f[u]$ 的首地址等于 $f[v]$ 的首地址往前挪一位：f[v] = f[u] + 1。

这样，$f[v][i]$ 天然就是 $f[u][i+1]$，我们连赋值的操作都省了，时间复杂度直接降为 $O(1)$！

对于其他的轻儿子，我们再老老实实开辟新的内存空间计算，计算完后暴力累加到 $f[u]$ 中。

因为每个节点只会位于一条长链中，合并轻链的代价实际上就是整棵树所有长链的总长度，而所有长链长度之和正好等于 $N$。因此，整体的时间复杂度被降到了 $O(N)$。

假设有这样一棵树：

      1
     / \
    2   4
   /
  3

内存分配与计算过程：

1. 我们为链 1 -> 2 -> 3 分配一段连续的内存，比如叫 mem[0..2]。
   1. 让指针 $f[1]$ 指向 mem[0] ；
   2. 让指针 $f[2]$ 指向 mem[1] （即 f[1] + 1）；
   3. 让指针 $f[3]$ 指向 mem[2] （即 f[2] + 1）；
2. 计算 3： $f[3][0] = 1$。此时 mem[2] = 1。
3. 计算 2： $f[2][0] = 1$。此时 mem[1] = 1。因为 $f[2]$ 和 $f[3]$ 共享内存，此时 $f[2][1]$ 自动就是 $f[3][0]$ 的值，也就是 $1$。目前 $f[2] = \{1, 1\}$，最大值为 $1$，为了下标最小，节点 $2$ 的答案取 $ans[2] = 0$。
4. 计算 4（轻儿子）： 另起炉灶，分配一块新内存 mem[3]。$f[4][0] = 1$。
5. 计算 1： $f[1][0] = 1$。此时 mem[0] = 1。继承重儿子 $2$ 的结果，此时 $f[1]$ 自动包含了 $\{1, 1, 1\}$（分别对应深度 $0, 1, 2$）。接着，我们把轻儿子 $4$ 的信息合并进来：$4$ 是 $1$ 的轻儿子，距离差为 $1$，所以把 $f[4][0]$ 累加到 $f[1][1]$ 上：$f[1][1] += f[4][0]$。此时 $f[1] = \{1, 2, 1\}$。最大值是 $2$，出现在下标 $1$ 处，所以 $ans[1] = 1$。

具体实现上有两种方法：

1. 可以将二维数组 $f$ 改为一个一维的指针数组，并使用一个额外的一维内存池动态分配内存。

#include <iostream>
#include <vector>
using namespace std;

#define N 1000005

int n;
vector<int> tr[N];
// maxdep 记录子树的最大深度，son 记录重儿子（最深儿子）
int maxdep[N], son[N];
// 核心优化：指针数组 f 和一维内存池 mem
int *f[N];
int mem[N];
int *ptr = mem; // ptr 指向当前内存池未使用的起始位置
int ans[N];

// 第一次 DFS：预处理每个节点的深度和长儿子
void dfs(int u, int fa) {
    maxdep[u] = 1;
    for (int v : tr[u]) {
        if (v == fa) continue;
        dfs(v, u);
        // 如果子节点的深度更大，更新当前节点的最大深度和重儿子
        if (maxdep[v] + 1 > maxdep[u]) {
            maxdep[u] = maxdep[v] + 1;
            son[u] = v;
        }
    }
}

// 第二次 DFS：利用指针计算答案
void dp(int u, int fa) {
    f[u][0] = 1; // 节点 u 自身（距离为 0 的节点数为 1）
    // 如果有重儿子，先处理重儿子
    if (son[u]) {
        // 【核心操作】让重儿子的数组直接使用 u 的内存（往后错一位）
        f[son[u]] = f[u] + 1;
        dp(son[u], u);
        // 继承重儿子的最优答案，因为深度往下平移了 1，所以答案也要 +1
        ans[u] = ans[son[u]] + 1;
        // 细节处理：如果继承过来后最大节点数仍然为 1，根据题意应该取最小深度 0
        if (f[u][ans[u]] == 1) ans[u] = 0;
    }
    // 处理所有轻儿子
    for (int v : tr[u]) {
        if (v == fa || v == son[u]) continue;
        // 给轻儿子重新分配独立的一段内存，长度为其最大深度
        f[v] = ptr;
        ptr += maxdep[v];
        dp(v, u);
        // 将轻儿子的信息暴力合并到当前节点 u
        for (int j = 1; j <= maxdep[v]; j++) {
            f[u][j] += f[v][j - 1]; // 轻儿子的深度 j-1 相当于 u 的深度 j
            // 实时更新当前节点的最优答案
            if (f[u][j] > f[u][ans[u]] || (f[u][j] == f[u][ans[u]] && j < ans[u])) {
                ans[u] = j;
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    dfs(1, 0);
    // 为根节点 1 分配第一段初始内存
    f[1] = ptr;
    ptr += maxdep[1];
    dp(1, 0);
    // 输出每个节点的答案
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

2. 由于长链剖分同样可以使得同一条重链上的 $dfn$ 连续，那么也可以直接使用节点的 $dfn$ 作为内存地址，这样省去了手动分配地址的操作，代码变得更加简洁优美。

#include <iostream>
#include <vector>
using namespace std;

#define N 1000005

int n;
vector<int> tr[N];
int f[N];
int maxdep[N], son[N], dfn[N];
int ans[N];

void dfs(int u, int fa) {
    maxdep[u] = 1;
    for (int v : tr[u]) {
        if (v == fa) continue;
        dfs(v, u);
        if (maxdep[u] < maxdep[v] + 1) {
            maxdep[u] = maxdep[v] + 1;
            son[u] = v;
        }
    }
}

void dp(int u, int fa) {
    static int idx = 0;
    dfn[u] = ++idx;
    f[dfn[u]] = 1;
    if (son[u]) {
        f[dfn[son[u]]] = f[dfn[u]] + 1;
        dp(son[u], u);
        ans[u] = ans[son[u]] + 1;
        if (f[dfn[u] + ans[u]] == 1) ans[u] = 0;
    }
    // 暴力合并轻儿子
    for (int v : tr[u]) {
        if (v == fa || v == son[u]) continue;
        dp(v, u);
        for (int j = 1; j <= maxdep[v]; j++) {
            f[dfn[u] + j] += f[dfn[v] + j - 1];
            if (f[dfn[u] + j] > f[dfn[u] + ans[u]] || f[dfn[u] + j] == f[dfn[u] + ans[u]] && j < ans[u]) {
                ans[u] = j;
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        tr[u].push_back(v);
        tr[v].push_back(u);
    }
    dfs(1, 0);
    dp(1, 0);
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
}