#P8552. Rabbit
Rabbit
题目背景
“说实话,最喜欢你了;因为长得好看,所以最喜欢你了。
你的性格,我最喜欢了;虽然不太清楚,但是最喜欢了。”
赫尔德最近加入了一个奇怪的社区,那里面流行一种“配对追星”的活动。大家在人群中找到那个最耀眼的人,就作为自己的偶像了。
题目描述
赫尔德不知道这样是否好,为了研究这个活动,她想先从这个活动能持续多久开始研究。于是她抽象了这个问题。
给定一棵树,共 个点,分别编号为 。
每次操作,你需要选出三个点 将他们标记,满足:
- 是 到 简单路径上编号最大的点;
- 两两不同;
- 先前都没有被标记过。
问至多能进行多少次操作。
【提示】
树上 到 的简单路径是指一个数列 ,满足:
- ,;
- 其中没有重复元素;
- 对于所有 , 与 有边相连。
输入格式
本题有多组数据。
第一行是数据组数 ,接下来 组数据,每组数据格式如下:
第一行一个正整数 。
接下来 行,每行两个正整数 ,描述树上的一条连接 的边。
输出格式
对于每组数据输出一行一个非负整数,为答案。
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
提示
【样例解释】
对于第一组数据,可以选择 。
对于第三组数据,可以依次选择 ,。
【数据范围】
设 为每个测试点所有数据中 的和。
对于所有数据:,,。
$$\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} $$特殊限制 :保证树的形态是一条链,即树上不存在度数大于 2 的点。
特殊限制 :保证树随机生成:对于每个整数 ,均匀随机选择整数 并在 间连边,然后随机打乱点的编号。