CF2023E Tree of Life

在一个古老王国的中心，生长着传奇的生命之树——这是独一无二的存在，也是整个世界魔法力量的源泉。该树由 $ n $ 个节点组成，树的每个节点都是一个魔法源，通过魔法通道（边）连接到其他这样的源。树中总共有 $ n-1 $ 条通道，第 $ i $ 条通道连接节点 $ v_i $ 和 $ u_i $。此外，树中任意两个节点之间存在一条唯一的简单路径。 然而，这些通道中流动的魔法能量必须保持平衡；否则，生命之树的力量可能扰乱自然秩序，造成灾难性的后果。王国的智者们发现，当两条魔法通道汇聚到一个节点时，会在它们之间产生一种危险的“魔法共振振动”。为了保护生命之树并维持其平衡，必须选择几条路径并沿着它们进行特殊的仪式。路径是一个由不同节点 $ v_1, v_2, \ldots, v_k $ 组成的序列，其中每一对相邻节点 $ v_i $ 和 $ v_{i+1} $ 由一条通道连接。当智者们沿着这样的路径进行仪式时，对于每个 $ 1 \leq i \leq k - 2 $，通道 $ (v_i, v_{i+1}) $ 和 $ (v_{i+1}, v_{i+2}) $ 之间的共振振动会被阻断。 智者们的任务是选择最少数量的路径，并沿着它们进行仪式，以阻止所有的共振振动。这意味着，对于从单个节点发出的每一对通道，必须至少存在一条选定的路径包含这两条通道。 帮助智者们找到最少数量的路径，以确保生命之树的魔法平衡得以保持，其力量继续滋养整个世界！

每个测试由多个测试用例组成。第一行包含一个整数 $ t $（ $ 1 \leq t \leq 4 \cdot 10^4 $ ）——测试用例的数量。测试用例的描述如下。 每个测试用例的第一行包含一个整数 $ n $（ $ 2 \leq n \leq 5 \cdot 10^5 $ ）——生命之树中的节点数量。 接下来每个测试用例的 $ n - 1 $ 行中，第 $ i $ 行包含两个整数 $ v_i $ 和 $ u_i $（ $ 1 \leq v_i < u_i \leq n $ ）——连接节点 $ v_i $ 和 $ u_i $ 的通道。 保证在树中任意两节点之间存在一条唯一的简单路径。 保证所有测试用例中 $ n $ 的总和不超过 $ 5 \cdot 10^5 $。

对于每个测试用例，输出一个整数——智者们需要选择的最小路径数量，以防止灾难的发生。

在第一个测试用例中，有两个从单个节点发出的通道对：$ (1, 2) $ 和 $ (2, 3) ， (2, 3) $ 和 $ (3, 4) $。在路径 $ 1-2-3-4 $ 上进行仪式是足够的。因此，答案是 $ 1 $。 在第二个测试用例中，从单个节点发出的通道没有对，因此答案是 $ 0 $。 在第三个测试用例中，仪式可以沿着路径 $ 2-1-3 ， 2-1-4 $ 和 $ 3-1-4 $ 进行。