题目描述

一所学校前一段时间买了第一台计算机（所以这台计算机的 ID 是 1）。

近年来，学校又购买了 $N-1$ 台新计算机。

每台新计算机都与之前买进的计算机中的一台建立连接。

现在请你求出第 $i$ 台计算机到距离其最远的计算机的电缆长度。

例如，上图中距离计算机 1 最远的是计算机 4，因此 $S_1=3$；距离计算机 2 最远的是计算机 4 和 5，因此 $S_2=2$；距离计算机 3 最远的是计算机 5，所以 $S_3=3$；同理，我们也得到 $S_4=4，S_5=4$。

输入格式

输入包含多测试数据。

每组测试数据第一行包含整数 $N$。

接下来 $N-1$ 行，每行包含两个整数，第 $i$ 行的第一个整数表示第 $i$ 台电脑买入时连接的电脑编号，第二个整数表示这次连接花费的电缆长度。

输出格式

每组测试数据输出 $N$ 行。

第 $i$ 行输出第 $i$ 台电脑的 $S_i$。

样例

5
1 1
2 1
3 1
1 1

3
2
3
4
4

样例解释

输入

$N=5$ 连接信息：

• 第 2 台计算机连接第 1 台，电缆长度 1
• 第 3 台计算机连接第 2 台，电缆长度 1
• 第 4 台计算机连接第 3 台，电缆长度 1
• 第 5 台计算机连接第 1 台，电缆长度 1

构建树

根据输入，树的结构如下： 1 号计算机是根。 2 号连接 1 号（边权 1） 3 号连接 2 号（边权 1） 4 号连接 3 号（边权 1） 5 号连接 1 号（边权 1）

所以树形为：

    1
   / \
  2   5
 /
3
|
4

计算每个节点到最远节点的距离

• 节点 1：最远节点是 4，距离 = 1+1+1=3
• 节点 2：最远节点是 4 或 5，距离 = max(1+1, 1+1)=2
• 节点 3：最远节点是 5，距离 = 1+1+1=3
• 节点 4：最远节点是 5，距离 = 1+1+1+1=4
• 节点 5：最远节点是 4，距离 = 1+1+1+1=4

输出：

3
2
3
4
4

数据范围

• $1 \le N \le 10000$
• 电缆总长度不超过 $10^9$

算法分析

这是一个树的直径和相关距离计算问题。

对于树中的每个节点，需要求出它到其他所有节点的最远距离。

树的直径

树的直径是树中最长的简单路径长度。可以通过两次 DFS 或 BFS 求出：

1. 从任意节点（如 1 号）出发，找到距离它最远的节点 $u$。
2. 从 $u$ 出发，找到距离 $u$ 最远的节点 $v$，则 $u$ 和 $v$ 之间的路径就是树的直径。

每个节点的最远距离

对于树中任意节点 $x$，其到其他节点的最远距离有两种可能：

1. 到达直径一端 $u$ 的距离。
2. 到达直径另一端 $v$ 的距离。

因为树的直径是最长的路径，所以对于任意节点 $x$，其最远节点一定是直径的某个端点（$u$ 或 $v$）。证明：假设最远节点是 $w$，且 $w$ 不是直径端点，则路径 $x \to w$ 与直径相交于某点，可以推出矛盾或得到更长的直径。

因此，对于每个节点 $x$，最远距离 $S_x = \max(dist(x, u), dist(x, v))$。

算法步骤

1. 读入 $N$ 和连接信息，构建无向树（注意输入给出的是有向连接，但树是无向的，所以要建双向边）。
2. 从节点 1 开始 DFS/BFS，找到最远节点 $u$（记录距离）。
3. 从节点 $u$ 开始 DFS/BFS，找到最远节点 $v$，并记录 $u$ 到每个节点的距离 $dist1[i]$。
4. 从节点 $v$ 开始 DFS/BFS，记录 $v$ 到每个节点的距离 $dist2[i]$。
5. 对于每个节点 $i$，输出 $\max(dist1[i], dist2[i])$。

复杂度

• 三次 DFS/BFS，每个 $O(N)$。
• 总复杂度 $O(N)$，对于 $N \le 10000$ 很快。

实现细节

• 使用邻接表存储树，每条边记录终点和权值。
• 注意输入可能有多组测试数据，直到文件结束。
• 由于 $N$ 最大 10000，递归 DFS 可能导致栈溢出，建议用栈迭代或 BFS。

样例验证

对于样例，我们执行：

1. 从 1 出发，最远节点是 4（距离 3），所以 $u=4$。
2. 从 4 出发，最远节点是 5（距离 4），所以 $v=5$。
3. 计算 $dist1[i]$：从 4 出发到各节点距离：$dist1[1]=3, dist1[2]=2, dist1[3]=1, dist1[4]=0, dist1[5]=4$。
4. 计算 $dist2[i]$：从 5 出发到各节点距离：$dist2[1]=1, dist2[2]=2, dist2[3]=3, dist2[4]=4, dist2[5]=0$。
5. 取最大值：
   • 节点1: max(3,1)=3
   • 节点2: max(2,2)=2
   • 节点3: max(1,3)=3
   • 节点4: max(0,4)=4
   • 节点5: max(4,0)=4

符合输出。

总结

本题是树的直径经典应用，关键点在于理解每个节点的最远距离必然是到直径某一端的距离。通过三次遍历即可高效求解。