F · Folding Game of Ohto Ai：中文题面

本场总览 · QOJ 原题

时限 3 秒，内存限制 512 MB。中文内容依据本次提供的题面整理；以原题为准。

中文题面 #

给定一棵无根树。树中一条路径由互不相同的顶点顺次相连构成；包含顶点数最多的路径称为直径。

当前树不止一个顶点时，可以任选一条直径 $d_1,\ldots,d_k$，把直径上关于中点对称的顶点合并。形式上，定义

$f(v)=\begin{cases}d_{\min\{i,k-i+1\}},&v=d_i,\\v,&v\text{ 不在所选直径上}.\end{cases}$

新顶点集为 $\{f(v):v\in V\}$；原边 $\{u,v\}$ 变成 $\{f(u),f(v)\}$，若两端被合并成同一点则删去，重边只保留一条。直径以外的顶点不直接合并，但其连接位置随端点映射改变。题目保证折叠后仍是一棵树。

不断操作直到只剩一个顶点，求最多能操作多少次。每次都必须重新选择当前树的直径，不能任选普通路径。

输入、输出与约束 #

$1\le T\le3\times10^3$。每组先给出 $1\le N\le5\times10^4$，再给出 $N-1$ 条边，端点在 $[1,N]$ 内且不同，保证成树。所有测试的 $\sum N\le5\times10^4$。每组输出最多折叠次数。

样例 #

输入 1 #

3
1
5
1 2
1 3
1 4
4 5
13
1 2
2 3
3 4
2 5
5 6
5 7
1 8
8 9
9 10
8 11
11 12
11 13

输出 1 #

0
3
7

样例说明 #

第一组原本只有一个顶点，操作数为零。第二组可以取直径 $2,1,4,5$，合并 $2$ 与 $5$、$1$ 与 $4$，得到三点路径，再折成两点、最后一点，共三次。第三组答案为七。材料中的图示未包含在本地文本中，这里以定义和文字说明折叠含义。

整理进度 #

本批材料没有这道题的个人 C++ 文件，因此这里先保留中文题面与样例解释；不把题面整理记作已补题。赛时提交过程与赛后补题记录待补。