← 返回题目列表

Codeforces · 1800/G

G. 对称树

中文机器翻译题面 查看原题

孩子获得了一棵由 $$$n$$$ 顶点组成的树,根位于顶点 $$$1$$$。由于孩子非常喜欢对称的物体,所以他想知道这棵树是否对称。

比如上图中的树是对称的。

而且这张图中的树木并不对称。

形式上,如果存在满足以下条件的子级顺序,则树是对称的:

- 根的最左边子树的子树是最右边子树的镜像;
- 根的左第二个孩子的子树是根的右第二个孩子的子树的镜像;
- ...
- 如果根的子树数量是奇数,则中间子树的子树应该是对称的。

输入

输入数据的第一行包含单个整数 $$$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$$$) — 由边连接的顶点的索引。

保证所有情况下 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。

输出

输出$$$t$$$字符串,每个字符串都是对应测试用例的答案。作为答案,如果该树是对称的,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

6
6
1 5
1 6
1 2
2 3
2 4
7
1 5
1 3
3 6
1 4
4 7
4 2
9
1 2
2 4
2 3
3 5
1 7
7 6
7 8
8 9
10
2 9
9 10
2 3
6 7
4 3
1 2
3 8
2 5
6 5
10
3 2
8 10
9 7
4 2
8 2
2 1
4 5
6 5
5 7
1

输出 #1

YES
NO
YES
NO
NO
YES