给定一棵以 \(1\) 为根的树，统计每个节点的子树中所有点到该点距离相同的最多的距离，如果相等选择较小的

\(n\leq10^6\)

长链剖分，dp

---

APIO2019上讲的……

首先可以设计一个时空 \(O(n^2)\) 的dp，令 \(f_{u,\ k}\) 表示以 \(u\) 的子树内与它距离为 \(k\) 的点的个数，转移即为 \(f_{u,\ k}=\sum{f_{v,\ k-1}}\) ，算答案直接统计即可

这种问题的解法是用长链剖分的套路，先 \(O(1)\) 继承长儿子的贡献，合并转移剩下儿子的贡献

考虑这种做法的时间复杂度，每条长链只会被遍历一次，而长链点数之和是 \(O(n)\) 的，因此时空复杂度 \(O(n)\)

有一种较为优秀的实现方法是开内存池，将 \(f_u\) 看做指针，将 \(f_{son_u}\) 赋值 \(f_u+1\) 快速继承

此题 \(f_{u,\ ans_u}=1\) 需要特判

时间复杂度 \(O(n)\)

代码

#include 
    
     using namespace std;const int maxn = 1e6 + 10;int buf_dp[maxn], *dp[maxn], *it = buf_dp;int n, m, h[maxn], len[maxn], son[maxn], ans[maxn];struct edges {  int nxt, to;} e[maxn << 1];void addline(int u, int v) {  static int cnt;  e[++cnt] = edges{h[u], v}, h[u] = cnt;}void dfs(int u, int f) {  for (int i = h[u]; i; i = e[i].nxt) {    int v = e[i].to;    if (v != f) {      dfs(v, u);      if (len[son[u]] < len[v]) son[u] = v;    }  }  len[u] = len[son[u]] + 1;}void DP(int u, int f) {  *dp[u] = 1;  if (son[u]) {    dp[son[u]] = dp[u] + 1;    DP(son[u], u), ans[u] = ans[son[u]] + 1;  }  for (int i = h[u]; i; i = e[i].nxt) {    int v = e[i].to;    if (v != f && v != son[u]) {      dp[v] = it, it += len[v], DP(v, u);      for (int j = 1; j <= len[v]; j++) {        dp[u][j] += dp[v][j - 1];        if (dp[u][j] > dp[u][ans[u]] || (dp[u][j] == dp[u][ans[u]] && j < ans[u])) {          ans[u] = j;        }      }    }  }  if (dp[u][ans[u]] == 1) ans[u] = 0;}int main() {  scanf("%d", &n);  for (int i = 1; i < n; i++) {    int u, v;    scanf("%d %d", &u, &v);    addline(u, v), addline(v, u);  }  dfs(1, 0);  dp[1] = it, it += len[1];  DP(1, 0);  for (int i = 1; i <= n; i++) {    printf("%d\n", ans[i]);  }  return 0;}