3685: 树数树(第二轮03)
题目描述
牛牛有一棵 n 个点的有根树，根为 1。
我们称一个长度为 m 的序列 a 是好的，当且仅当：
• ∀i ∈ (1, m]， ai 为 ai−1的祖先或 ai−1是 ai 的祖先；
• ∀1 ≤ i < j ≤ m, ai ≠ aj 。
你需要帮助牛牛求出最长的序列长度。
输入
第一行一个正整数 T，表示数据组数。 对于每组数据第一行一个正整数 n。
接下来 n − 1行，每行两个正整数 u,v，表示树上的一条边。
输出
T 行，每行一个整数表示每组数据的答案。
样例输入 复制
1
8
5 3
1 5
4 5
2 5
1 6
8 7
7 6样例输出 复制
7提示
【样例 1 输入】
1
8
5 3
1 5
4 5
2 5
1 6
8 7
7 6
【样例 1 输出】
7
【样例 2 】
选手目录： https://uploadfiles.nowcoder.com/files/20211004/tree.zip 见选手目录下的 tree/tree2.in 和 tree/tree2.ans。
【样例 3 】
见选手目录下的 tree/tree3.in 和 tree/tree3.ans。 该样例满足特殊性质 A。
【样例 4 】
见选手目录下的 tree/tree4.in 和 tree/tree4.ans。 该样例满足特殊性质 B。
【样例 5 】
见选手目录下的 tree/tree5.in 和 tree/tree5.ans。 该样例满足特殊性质 C。
【数据范围】
对于 100% 的数据， 1 ≤ T ≤ 5， 2 ≤ n ≤ 105， 1 ≤ u, v ≤ n， u ≠ v，输入保证是 一棵树。
特殊性质 A：给出的树为链，其中 1 号点的度数为 1。
特殊性质 B：给出的树为菊花，其中 1 号点的度数为 n − 1。
特殊性质 C：给出的数为完全二叉树。