g7-07690. 树的高度 · 林老师的题库

题目描述

给定一棵有 $n$ 个结点的树，结点编号为 $1, 2, \dots, n$ ，其中 $1$ 号结点是根。

对于结点 $u$ ，定义它的高度 $h (u)$ 为：从 $u$ 出发，每次只能走向自己的儿子，走到某个叶子结点时经过的边数的最大值。若 $u$ 没有儿子（即 $u$ 是叶子），则规定 $h (u) = 0$ 。

请对每个结点求出它的高度。

第一行一个整数 $n$ 。

接下来 $n - 1$ 行，每行两个整数 $u, v$ （ $1 \leq u, v \leq n$ ），表示结点 $u$ 与结点 $v$ 之间有一条边。

保证给出的图是一棵以 $1$ 为根的树。

输出 $n$ 行，第 $i$ 行一个整数，表示结点 $i$ 的高度 $h (i)$ 。

输入

输出

样例解释：结点 $3, 4, 5$ 都没有儿子，高度为 $0$ ；结点 $2$ 的儿子 $4, 5$ 的高度都是 $0$ ，所以 $h (2) = 0 + 1 = 1$ ；结点 $1$ 的儿子 $2, 3$ 中 $h (2) = 1$ 最大，所以 $h (1) = 1 + 1 = 2$ 。

样例解释：只有一个结点，它既是根也是叶子，高度为 $0$ 。

对于 $100%$ 的数据， $1 \leq n \leq 2 \times 1 0^{5}$ 。

本题共 $10$ 个测试点，每个测试点 $10$ 分。