无根之宴

节点累积完了，但树是无根的——需要换根。

"无根？"CC问。

"对。"你说，"树没有固定的根，每个节点都可以当根。"

"换根？"

"对。"你说，"先任选一个根做一次DP，然后再做一次DP，把根换到每个子节点。"

"两次？"

"对。"你说，"第一次算子树信息，第二次算父节点方向的信息。"

"第47个节点。"你说，"如果它是根，整棵树的高度是多少？"

"看最远叶子。"你说，"换根后，从47出发，最远能到哪。"

"咋算？"

"两次DFS。"你说，"第一次算每个节点的子树高度，第二次换根，算父方向的高度。"

"$O(n)$？"

"对。"你说，"每个节点访问常数次。"

"无根之宴？"

"对。"你说，"每个节点都可以当主人——轮流坐庄。"

"公平？"

"对。"你说，"每个节点都有机会当根，信息都被考虑到。"

"像轮流请客？"

"对。"你说，"像轮流请客——今天你家，明天我家。"

"吃啥？"

"数据。"你说，"吃的是树的信息——高度、深度、子树大小。"

CC看着那棵无根树——像一片云，像一张网，像某种没有中心的东西。

"中心在哪？"她问。

"任意。"你说，"也可以找树的中心——直径的中点。"

"直径？"

"对。"你说，"树中最长的路径。"

"找得到？"

"对。"你说，"两次BFS或DFS。"

Echo把换根过程投射出来——根在节点间跳动，像篝火，像聚光灯。

"以前我固定在一个点。"她说，"现在……在动。"

"因为你在探索。"CC说。

"对。"Echo说，"因为我在探索。

题目描述

给定一棵树，对每个节点作为根，求树的高度（最远叶子距离）。

输入格式

第一行$n$。接下来$n-1$行，每行一条边。

输出格式

$n$行，第$i$行表示以$i$为根的高度。

输入样例

5
1 2 3 4 5

输出样例

1

提示

• 换根DP：第一次DFS算子树高度，第二次DFS换根。
• $dp2[v]=\max(dp2[u]+1,\text{次大子树高度}+1)$。
• 时间复杂度$O(n)$。