P8552 Rabbit

"To be honest, I like you the most; because you look good, I like you the most. Your personality, I like it the most; although I do not really understand it, I still like it the most." Helde has recently joined a strange community where an activity called "paired idol-chasing" is popular. Everyone looks for the most eye-catching person in the crowd and treats them as their idol.

Helde is not sure whether this is a good thing. To study how this activity works, she wants to start by studying how long it can last, so she abstracted it into the following problem. Given a tree with $n$ nodes, numbered $1 \sim n$. In each operation, you need to choose three nodes $a, b, c$ and mark them, such that: - $c$ is the node with the largest label on the simple path from $a$ to $b$; - $a$, $b$, and $c$ are pairwise distinct; - $a$, $b$, and $c$ have not been marked before. Ask for the maximum number of operations that can be performed. --- **Hint** A simple path from $p$ to $q$ in a tree refers to a sequence $a_1, \dots, a_k$ that satisfies: 1. $a_1 = p$, $a_k = q$; 2. there are no repeated elements; 3. for all $1 \le i < k$, $a_{i+1}$ is connected to $a_i$ by an edge.

This problem contains multiple test cases. The first line contains the number of test cases $T$. Then follow $T$ test cases, each in the following format: The first line contains a positive integer $n$. In the next $n - 1$ lines, each line contains two positive integers $x, y$, describing an edge connecting $x$ and $y$ in the tree.

For each test case, output one line containing one non-negative integer, the answer.

**Sample Explanation** For the first test case, you can choose $a = 1, b = 2, c = 3$. For the third test case, you can choose in order $a = 3, b = 4, c = 7$, and $a = 1, b = 2, c = 5$. --- **Constraints** Let $S$ be the sum of $n$ over all test cases within a test point. For all testdata: $1 \le T \le 3 \times 10^4$, $1 \le n \le 2 \times 10^5$, $S \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} $$ Special restriction $\textsf{A}$: the tree is guaranteed to be a chain, meaning there is no node in the tree with degree greater than $2$. Special restriction $\textsf{B}$: the tree is guaranteed to be generated randomly: for each integer $i \in [2, n]$, uniformly randomly choose an integer $j \in [1, i - 1]$ and add an edge between $i$ and $j$, then randomly shuffle the node labels. Translated by ChatGPT 5