Tree of Life
Contest: Codeforces Round 980 (Div. 1)
Difficulty rating: 3300
Tags: dp, greedy, trees

In the heart of an ancient kingdom grows the legendary Tree of Life — the only one of its kind and the source of magical power for the entire world. The tree consists of $$$n$$$ nodes. Each node of this tree is a magical source, connected to other such sources through magical channels (edges). In total, there are $$$n-1$$$ channels in the tree, with the $$$i$$$-th channel connecting nodes $$$v_i$$$ and $$$u_i$$$. Moreover, there exists a unique simple path through the channels between any two nodes in the tree.

However, the magical energy flowing through these channels must be balanced; otherwise, the power of the Tree of Life may disrupt the natural order and cause catastrophic consequences. The sages of the kingdom discovered that when two magical channels converge at a single node, a dangerous "magical resonance vibration" occurs between them. To protect the Tree of Life and maintain its balance, it is necessary to select several paths and perform special rituals along them. A path is a sequence of distinct nodes $$$v_1, v_2, \ldots, v_k$$$, where each pair of adjacent nodes $$$v_i$$$ and $$$v_{i+1}$$$ is connected by a channel. When the sages perform a ritual along such a path, the resonance vibration between the channels $$$(v_i, v_{i+1})$$$ and $$$(v_{i+1}, v_{i+2})$$$ is blocked for each $$$1 \leq i \leq k - 2$$$.

The sages' task is to select the minimum number of paths and perform rituals along them to block all resonance vibrations. This means that for every pair of channels emanating from a single node, there must exist at least one selected path that contains both of these channels.

Help the sages find the minimum number of such paths so that the magical balance of the Tree of Life is preserved, and its power continues to nourish the entire world!

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 4 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 5 \cdot 10^5$$$) — the number of nodes in the Tree of Life.

The $$$i$$$-th of the following $$$n - 1$$$ lines of each test case contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \leq v_i < u_i \leq n$$$) — the channel connecting nodes $$$v_i$$$ and $$$u_i$$$.

It is guaranteed that there exists a unique simple path through the channels between any two nodes.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the minimum number of paths that the sages need to select to prevent a catastrophe.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, there are two pairs of channels emanating from a single node: $$$(1, 2)$$$ and $$$(2, 3)$$$, $$$(2, 3)$$$ and $$$(3, 4)$$$. It is sufficient to perform the ritual along the path $$$1-2-3-4$$$. Thus, the answer is $$$1$$$.

In the second test case, there are no pairs of channels emanating from a single node, so the answer is $$$0$$$.

In the third test case, rituals can be performed along the paths $$$2-1-3$$$, $$$2-1-4$$$, and $$$3-1-4$$$.

Example input:
5
4
1 2
2 3
3 4
2
1 2
4
1 2
1 3
1 4
8
3 7
2 4
1 2
2 5
3 6
1 3
3 8
6
2 3
1 2
3 6
1 5
1 4

Example output:
1
0
3
7
3

Editorial:
This problem has several solutions that are similar to varying degrees. We will describe one of them.
We will apply the following greedy approach. We will construct the answer by combining the answers for the subtrees. To do this, we will perform a depth-first traversal, and when exiting a vertex, we return a triplet $$$(ans, up, bonus)$$$, where $$$ans$$$ is the minimum number of paths needed to cover all pairs of adjacent edges in the subtree (considering the edge upwards), $$$up$$$ is the number of edges upwards, and $$$bonus$$$ is the number of paths that are connected at some vertex of the subtree but can be separated into two paths upwards without violating the coverage.
Then, if we are at vertex $$$v$$$ and receive from child $$$u$$$ the triplet $$$(ans_u, up_u, bonus_u)$$$, we need to increase $$$up_u$$$ to at least $$$deg_v - 1$$$ (to satisfy the coverage). Next, we will effectively reduce it by $$$deg_v - 1$$$, implying that we have satisfied all such pairs. Meanwhile, we will sum $$$ans_u$$$ and $$$bonus_u$$$, and subtract from $$$ans$$$ when connecting. We first increase using $$$bonus$$$ ($$$ans_u += 1, up_u += 2, bonus_u -= 1$$$), and then simply by adding new paths.
After this, we have remaining excess paths ($$$up$$$) leading to $$$v$$$, which we might be able to combine to reduce the answer. This is represented by the set $$$U = \{up_{u_1}, up_{u_2}, \ldots, up_{u_k}\}$$$. If $$$\max(U) * 2 \leq sum(U)$$$, we can combine all pairs (leaving at most $$$1$$$ path upwards) in $$$U$$$, adding these paths to $$$bonus_v$$$. Otherwise, we increase all $$$up_{u_i} \neq \max(U)$$$ using $$$bonus_{u_i}$$$ until $$$\max(U) * 2 \leq sum(U)$$$ is satisfied. Finally, we return $$$up_v = (sum(U) \mod 2) + deg_v - 1$$$ if the condition is met, and $$$up_v = 2 * \max(U) - sum(U) + deg_v - 1$$$, while $$$bonus_v$$$ and $$$ans_v$$$ are the sums that may have changed during the process. Don't forget to account for the paths that merged at $$$v$$$.
The root needs to be handled separately, as there are no paths upwards there.
To prove this solution, one can consider $$$dp_{v, up}$$$ — the minimum number of paths needed to cover subtree $$$v$$$ if $$$up$$$ paths go upwards. It is not hard to notice that the triplet $$$(ans, up, bonus)$$$ in the greedy solution describes all optimal states of the dynamic programming.
P.S. Strict proofs are left as an exercise for the reader.