{"raw_statement":[{"iden":"background","content":"“说实话，最喜欢你了；因为长得好看，所以最喜欢你了。\n\n你的性格，我最喜欢了；虽然不太清楚，但是最喜欢了。”\n\n赫尔德最近加入了一个奇怪的社区，那里面流行一种“配对追星”的活动。大家在人群中找到那个最耀眼的人，就作为自己的偶像了。"},{"iden":"statement","content":"赫尔德不知道这样是否好，为了研究这个活动，她想先从这个活动能持续多久开始研究。于是她抽象了这个问题。\n\n给定一棵树，共 $n$ 个点，分别编号为 $1\\sim n$。\n\n每次操作，你需要选出三个点 $a,b,c$ 将他们标记，满足：\n\n- $c$ 是 $a$ 到 $b$ 简单路径上编号最大的点；\n- $a,b,c$ 两两不同；\n- $a,b,c$ 先前都没有被标记过。\n\n问至多能进行多少次操作。\n\n---\n\n**【提示】**\n\n树上 $p$ 到 $q$ 的简单路径是指一个数列 $a_1,\\dots,a_k$，满足：\n\n1. $a_1=p$，$a_k=q$；\n2. 其中没有重复元素；\n3. 对于所有 $1\\le i<k$，$a_{i+1}$ 与 $a_i$ 有边相连。"},{"iden":"input","content":"本题有多组数据。\n\n第一行是数据组数 $T$，接下来 $T$ 组数据，每组数据格式如下：\n\n第一行一个正整数 $n$。\n\n接下来 $n-1$ 行，每行两个正整数 $x,y$，描述树上的一条连接 $x,y$ 的边。"},{"iden":"output","content":"对于每组数据输出一行一个非负整数，为答案。"},{"iden":"note","content":"**【样例解释】**\n\n对于第一组数据，可以选择 $a=1,b=2,c=3$。\n\n对于第三组数据，可以依次选择 $a=3,b=4,c=7$，$a=1,b=2,c=5$。\n\n---\n\n**【数据范围】**\n\n设 $S$ 为每个测试点所有数据中 $n$ 的和。\n\n对于所有数据：$1\\le T\\le 3\\times 10^4$，$1\\le n\\le 2\\times 10^5$，$S\\le 6\\times 10^5$。\n\n$$\n\\begin{array}{c|c|c|c|c|c} \\hline\n\\textbf{子任务编号} & ~~~~~~~n\\le ~~~~~~~ & ~~~~~~~S\\le ~~~~~~~ & \\textbf{特殊性质} & \\textbf{子任务依赖} & \\textbf{~~~分数~~~} \\\\ \\hline\n\\textsf{1} & 5 & & & & 3 \\\\ \\hline\n\\textsf{2} & 20 & 60 & & & 5 \\\\ \\hline\n\\textsf{3} & & & \\textsf{B} & & 12 \\\\ \\hline\n\\textsf{4} & 333 & 10^3 & \\textsf{A} & & 9 \\\\ \\hline\n\\textsf{5} & 333 & 10^3 & & \\textsf{2,4} & 7 \\\\ \\hline\n\\textsf{6} & 3333 & 10^4 & \\textsf{A} & \\textsf{4} & 15 \\\\ \\hline\n\\textsf{7} & 3333 & 10^4 & & \\textsf{5,6} & 13 \\\\ \\hline\n\\textsf{8} & & & \\textsf{A} & \\textsf{6} & 12 \\\\ \\hline\n\\textsf{9} & & & & \\textsf{1,3,7,8} & 24 \\\\ \\hline\n\\end{array}\n$$\n\n特殊限制 $\\textsf{A}$：保证树的形态是一条链，即树上不存在度数大于 2 的点。\n\n特殊限制 $\\textsf{B}$：保证树随机生成：对于每个整数 $i\\in [2,n]$，均匀随机选择整数 $j\\in [1,i-1]$ 并在 $i,j$ 间连边，然后随机打乱点的编号。"}],"translated_statement":null,"sample_group":[["3\n3\n2 3\n1 3\n4\n2 3\n3 4\n4 1\n7\n2 5\n5 1\n2 6\n2 3\n7 4\n3 7\n","1\n1\n2\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}