#P8552. Rabbit

Rabbit

题目背景

“说实话,最喜欢你了;因为长得好看,所以最喜欢你了。

你的性格,我最喜欢了;虽然不太清楚,但是最喜欢了。”

赫尔德最近加入了一个奇怪的社区,那里面流行一种“配对追星”的活动。大家在人群中找到那个最耀眼的人,就作为自己的偶像了。

题目描述

赫尔德不知道这样是否好,为了研究这个活动,她想先从这个活动能持续多久开始研究。于是她抽象了这个问题。

给定一棵树,共 nn 个点,分别编号为 1n1\sim n

每次操作,你需要选出三个点 a,b,ca,b,c 将他们标记,满足:

  • ccaabb 简单路径上编号最大的点;
  • a,b,ca,b,c 两两不同;
  • a,b,ca,b,c 先前都没有被标记过。

问至多能进行多少次操作。


【提示】

树上 ppqq 的简单路径是指一个数列 a1,,aka_1,\dots,a_k,满足:

  1. a1=pa_1=pak=qa_k=q
  2. 其中没有重复元素;
  3. 对于所有 1i<k1\le i<kai+1a_{i+1}aia_i 有边相连。

输入格式

本题有多组数据。

第一行是数据组数 TT,接下来 TT 组数据,每组数据格式如下:

第一行一个正整数 nn

接下来 n1n-1 行,每行两个正整数 x,yx,y,描述树上的一条连接 x,yx,y 的边。

输出格式

对于每组数据输出一行一个非负整数,为答案。

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

1
1
2

提示

【样例解释】

对于第一组数据,可以选择 a=1,b=2,c=3a=1,b=2,c=3

对于第三组数据,可以依次选择 a=3,b=4,c=7a=3,b=4,c=7a=1,b=2,c=5a=1,b=2,c=5


【数据范围】

SS 为每个测试点所有数据中 nn 的和。

对于所有数据:1T3×1041\le T\le 3\times 10^41n2×1051\le n\le 2\times 10^5S6×105S\le 6\times 10^5

$$\begin{array}{c|c|c|c|c|c} \hline \textbf{子任务编号} & ~~~~~~~n\le ~~~~~~~ & ~~~~~~~S\le ~~~~~~~ & \textbf{特殊性质} & \textbf{子任务依赖} & \textbf{~~~分数~~~} \\ \hline \textsf{1} & 5 & & & & 3 \\ \hline \textsf{2} & 20 & 60 & & & 5 \\ \hline \textsf{3} & & & \textsf{B} & & 12 \\ \hline \textsf{4} & 333 & 10^3 & \textsf{A} & & 9 \\ \hline \textsf{5} & 333 & 10^3 & & \textsf{2,4} & 7 \\ \hline \textsf{6} & 3333 & 10^4 & \textsf{A} & \textsf{4} & 15 \\ \hline \textsf{7} & 3333 & 10^4 & & \textsf{5,6} & 13 \\ \hline \textsf{8} & & & \textsf{A} & \textsf{6} & 12 \\ \hline \textsf{9} & & & & \textsf{1,3,7,8} & 24 \\ \hline \end{array} $$

特殊限制 A\textsf{A}:保证树的形态是一条链,即树上不存在度数大于 2 的点。

特殊限制 B\textsf{B}:保证树随机生成:对于每个整数 i[2,n]i\in [2,n],均匀随机选择整数 j[1,i1]j\in [1,i-1] 并在 i,ji,j 间连边,然后随机打乱点的编号。