#P9624. 树数树

    ID: 6241 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-树形 DP差分转化左偏树堆合并

树数树

题目描述

牛牛有一棵 nn 个点的有根树,根为 11。

我们称一个长度为 mm 的序列 aa 是好的,当且仅当:

  • ∀i∈(1,m]\forall i\in(1,m],aia_i 为 ai−1a_{i-1} 的祖先或 ai−1a_{i-1} 是 aia_i 的祖先;
  • ∀1≤i<j≤m\forall 1\le i<j\le m,ai≠aja_i\not=a_j。

你需要帮助牛牛求出最长的好的序列长度。

输入格式

第一行一个正整数 TT,表示数据组数。

对于每组数据第一行一个正整数 nn。

接下来 n−1n-1 行,每行两个正整数 u,vu,v,表示树上的一条边。

输出格式

TT 行,每行一个整数表示每组数据的答案。

样例

1
8
5 3
1 5
4 5
2 5
1 6
8 7
7 6
7

另有 44 组大样例在题目附件中,其中样例 3,4,53,4,5 分别满足下面的特殊性质 A,B,C\text{A,B,C}。

数据范围

对于 100%100\% 的数据,1≤T≤51\le T\le 5,2≤n≤1052\le n\le 10^5,1≤u,v≤n1\le u,v\le n,u≠vu\not=v,输入保证是一棵树。

数据点编号 n≤n\le 其他限制
1∼21\sim 2 1010 无
3∼63\sim 6 2×1032\times 10^3
7∼107\sim 10 10510^5 特殊性质 A\text{A}
11∼1211\sim 12 特殊性质 B\text{B}
13∼1413\sim 14 特殊性质 C\text{C}
15∼2015\sim 20 无

特殊性质 A\text{A}:给出的树为链,其中 11 号点的度数为 11。

特殊性质 B\text{B}:给出的树为菊花,其中 11 号点的度数为 n−1n-1。

特殊性质 C\text{C}:给出的树为完全二叉树。