5215. 树的距离(Tree Distances I)
时间限制:1000 MS 内存限制:512 MB
题目描述
## 题目描述 给定一棵由 $n$ 个节点组成的无根树。 你的任务是:对于每个节点,求出它到树中其他任意节点的最大距离(即到其他节点的最长简单路径的边数)。 ## 输入格式 第一行包含一个整数 $n$,表示树中节点的数量。节点编号为 $1, 2, \dots, n$。 接下来 $n - 1$ 行,每行包含两个整数 $a$ 和 $b$,表示节点 $a$ 和 $b$ 之间有一条无向边。 ## 输出格式 输出一行由空格分隔的 $n$ 个整数,依次表示节点 $1, 2, \dots, n$ 到其他节点的最大距离。 ## 输入输出样例 ### 输入样例 1 ``` 5 1 2 1 3 3 4 3 5 ``` ### 输出样例 1 ``` 2 3 2 3 3 ``` ## 提示/说明 ### 样例 1 解释 给定树的结构如下: - $1$ 与 $2, 3$ 相连; - $3$ 与 $4, 5$ 相连。 各节点到其他所有节点的最长路径计算如下: - **节点 $1$**:到节点 $2$ 的距离为 $1$,到节点 $3$ 的距离为 $1$,到节点 $4, 5$ 的距离均为 $2$。最大距离为 $2$。 - **节点 $2$**:到节点 $1$ 的距离为 $1$,到节点 $3$ 的距离为 $2$,到节点 $4, 5$ 的距离均为 $3$。最大距离为 $3$(路径为 $2 \to 1 \to 3 \to 4$ 或 $2 \to 1 \to 3 \to 5$)。 - **节点 $3$**:到节点 $1$ 的距离为 $1$,到节点 $2$ 的距离为 $2$,到节点 $4, 5$ 的距离均为 $1$。最大距离为 $2$。 - **节点 $4$**:到节点 $3$ 的距离为 $1$,到节点 $1, 5$ 的距离均为 $2$,到节点 $2$ 的距离为 $3$。最大距离为 $3$。 - **节点 $5$**:到节点 $3$ 的距离为 $1$,到节点 $1, 4$ 的距离均为 $2$,到节点 $2$ 的距离为 $3$。最大距离为 $3$。 因此,依次输出 `2 3 2 3 3`。 ### 数据规模与约定 对于所有数据,保证: - $1 \le n \le 2 \times 10^5$; - $1 \le a, b \le n$,且 $a \neq b$; - 输入数据保证构成一棵合法的无根树。