CF1800G Symmetree

Kid 得到了一棵有 $n$ 个结点的树，根节点为 $1$。由于他非常喜欢对称的物体，Kid 想知道这棵树是否是对称的。  例如，上图中的树是对称的。 而下图中的树不是对称的。形式化地说，如果存在一种对子节点的排列方式，使得： - 根节点最左侧子节点的子树与最右侧子节点的子树互为镜像； - 根节点次左侧子节点的子树与次右侧子节点的子树互为镜像； - 以此类推； - 如果根节点的子节点数为奇数，则中间子节点的子树本身也必须是对称的。 那么这棵树就是对称的。

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示树的结点数。 接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \neq v$），表示一条连接结点 $u$ 和 $v$ 的边。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出 $t$ 行，每行对应一个测试用例的答案。如果该树是对称的，输出 "YES"，否则输出 "NO"。 你可以以任意大小写输出答案（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定答案）。

由 ChatGPT 4.1 翻译