Problem H. 你说的对，但是无法平衡 I

时间限制 : 2000 ms

空间限制 : 256 MB

题目描述

二叉树的结点的平衡因子定义为该结点左子树深度与右子树深度之差，其中空树的深度是 $0$。

如果对于树的每个结点而言，平衡因子均在 $[-1, 1]$ 之间，则这棵树是 深度平衡 的。

如果对于树的每个结点而言，平衡因子均为 $0$，则这棵树是 完全深度平衡 的。

现给定一棵以 $1$ 为根的二叉树，根结点的深度为 $1$，根结点的孩子的深度为 $2$，以此类推。

接下来，你可以进行任意次删边操作，每次操作中：

• 选择一条边 $(u, v)$，然后删去它。删除后，这棵二叉树将分为两个部分。对于每个部分，删除前深度最低的点将作为该部分的根结点。

你的目标是进行若干删边操作，使得：

• 得到的二叉森林中，所有二叉树都是 完全深度平衡 的。

求最少需要的操作次数。

输入格式

第一行一个整数 $T$，表示数据组数。

对于每组数据：第一行包含一个整数 $n$，表示树的结点数。

接下来 $n - 1$ 行两个整数 $u, v$，表示树的一条边。

保证给定的是一棵二叉树，根结点为 $1$。

输出格式

对于每组数据，输出一行，仅包含一个整数，表示最少操作次数。

样例输入1

2
7
2 1
1 3
6 7
4 6
5 4
2 4
3
1 2
2 3

样例输出1

2
2

样例 1 解释

如图，切断（2,4），则 4 成为剩余部分新的根结点；

切断（6,7），则 7 成为剩余部分新的根结点。

若如此做，以 1, 4, 7 为根结点的三个部分均是完全深度平衡的。

对于第二组样例，两条边均需要删除。

数据范围与约定

$1\le T\le 5\times 10^4$

$1\le n\le 2\times 10^5$

$1\le u,v\le n$

保证给出的是一棵以 $1$ 为根结点的 二叉树。

保证所有测试点中 $n$ 的总和不超过 $2\times 10^5$。