A6055 | $「2017 山东一轮集训 Day3」第二题$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

对于一棵有根树，定义一个点 $u$ 的 $k \text{ −}$ 子树为 $u$ 的子树中距离 $u$ 不超过 $k$ 的部分。注意，假如 $u$ 的子树中不存在距离 $u$ 为 $k$ 的点，则 $u$ 的 $k \text{ −}$ 子树是不存在的。 定义两棵子树是相同的，当且仅当不考虑点的标号时，他们的形态是相同的（儿子的顺序也需要考虑）。给定一棵 $n$ 个点，点的标号在 $[1, n]$，以 $1$ 为根的有根树。问最大的 $k$，使得存在两个点 $u \neq v$，满足 $u$ 的 $k \text{−}$ 子树与 $v$ 的 $k \text{ −}$ 子树相同。

第一行输入一个正整数 $n$。 接下来读入 $n$ 个部分，第 $i$ 个部分描述点 $i$ 的儿子，且以顺序给出。 每个部分首先读入一个整数 $x$，代表儿子个数。接下来 $x$ 个整数，代表从左到右儿子的标号。

输出一个整数 $k$，代表最大的合法的 $k$。

输入 #1

输出 #1

C++ 编辑器

输入

输出