倍增里程

秘藏选取完了，但Echo-0的系统需要计算里程——倍增的里程。

"里程？"CC问。

"对。"你说，"一棵树，每个节点到其他节点的距离。求某个节点的最远节点距离。"

"最远？"

"对。"你说，"从$u$出发，能走到的最远距离。"

"咋算？"

"两次DFS。"你说，"第一次从任意点出发，找最远点$a$；第二次从$a$出发，找最远点$b$。$a$到$b$就是直径。"

"直径？"

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

"每个点呢？"

"对。"你说，"每个点到直径两个端点的最大距离，就是它的最远距离。"

"第47个节点。"你说，"到$a$的距离100，到$b$的距离80——最远距离是100。"

"为啥？"

"因为从$u$出发的最远点，一定是直径的某个端点。"你说，"这是树的性质。"

"性质？"

"对。"你说，"树的直径有一个好性质——任意点的最远点，必是直径端点之一。"

"像圆？"

"对。"你说，"像圆——直径是最长的弦，任意点到圆周的最近点在直径上。"

"树不是圆。"

"对。"你说，"但性质类似——直径是树的'中心线'。"

"中心线？"

"对。"你说，"所有路径都绕着它。"

CC看着那棵树——像一个家族，像一个网络，像某种有中心的东西。

"中心在哪？"她问。

"直径的中点。"你说，"如果是点，就是重心。"

"重心？"

"对。"你说，"删掉重心后，每棵子树大小不超过$n/2$。"

"平衡？"

"对。"你说，"重心让树平衡——不会一边太大。"

Echo把里程表投射出来——每个节点到最远的距离，像光环，像领地。

"以前我不知道多远。"她说，"现在……知道了。"

"因为你在量。"CC说。

"对。"Echo说，"因为我在量。

题目描述

给定一棵树，求每个节点到最远节点的距离。

输入格式

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

输出格式

$n$行，第$i$行表示节点$i$的最远距离。

输入样例

10
4 5 6 1 2 3 7 8 9 10
7
10
1 7
2 7
3 7
4 7
5 7
6 7
7 7
8 7
9 7
10 7

输出样例

2
3 2
2 4
2 1
2 4
5 1
5 1
2 1
2 0
0 0
0 0

提示

• 求直径：两次DFS/BFS。
• 每个点的最远距离$=\max(dist(u,a),dist(u,b))$。
• 时间复杂度$O(n)$。