310215: CF1800G. Symmetree
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Symmetree
题意翻译
给定一棵树，$1$ 为根。你可以调整一个点的儿子顺序，问这棵树是否有可能对称。 一棵树对称，如果根满足： * 根最左边的儿子的子树与最右边的儿子的子树成镜像。 * 根左边第二个的儿子的子树与右边第二个儿子的子树成镜像。 ........ * 如果儿子个数为奇数，那么中间的儿子的子树也满足对称。题目描述
Kid was gifted a tree of $ n $ vertices with the root in the vertex $ 1 $ . Since he really like symmetrical objects, Kid wants to find out if this tree is symmetrical.  For example, the trees in the picture above are symmetrical.  And the trees in this picture are not symmetrical.Formally, a tree is symmetrical if there exists an order of children such that: - The subtree of the leftmost child of the root is a mirror image of the subtree of the rightmost child; - the subtree of the second-left child of the root is a mirror image of the subtree of the second-right child of the root; - ... - if the number of children of the root is odd, then the subtree of the middle child should be symmetrical.输入输出格式
输入格式
The first line of input data contains single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases in the test. The first line of each case contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree. The following $ n-1 $ lines contain two integers each $ u $ and $ v $ ( $ 1 \le u, v \le n $ , $ u \neq v $ ) — indices of vertices connected by an edge. It is guaranteed that the sum of $ n $ over all cases does not exceed $ 2 \cdot 10^5 $ .
输出格式
Output $ t $ strings, each of which is the answer to the corresponding test case. As an answer, output "YES" if this tree is symmetrical, and "NO" otherwise. You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
输入输出样例
输入样例 #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
YESInput
题意翻译
给定一棵树，$1$ 为根。你可以调整一个点的儿子顺序，问这棵树是否有可能对称。 一棵树对称，如果根满足： * 根最左边的儿子的子树与最右边的儿子的子树成镜像。 * 根左边第二个的儿子的子树与右边第二个儿子的子树成镜像。 ........ * 如果儿子个数为奇数，那么中间的儿子的子树也满足对称。Output
**题意翻译**
给定一棵树，1号为根。你可以调整一个点的儿子顺序，问这棵树是否有可能对称。
一棵树对称，如果根满足：
- 根最左边的儿子的子树与最右边的儿子的子树成镜像。
- 根左边第二个的儿子的子树与右边第二个儿子的子树成镜像。
........
- 如果儿子个数为奇数，那么中间的儿子的子树也满足对称。
**题目描述**
Kid得到了一棵有n个顶点的树，1号顶点为根。因为他非常喜欢对称的物体，所以他想知道这棵树是否对称。
在这个图中的树是不对称的。形式上，如果存在一个孩子的顺序使得：
- 根的最左边的孩子的子树是根的最右边孩子的子树的镜像；
- 根的第二个左边的孩子的子树是根的第二个右边的孩子的子树的镜像；
- ...
- 如果根的孩子数是奇数，那么根的中间孩子的子树也应该是对称的。
**输入输出格式**
**输入格式**
输入数据的第一行包含单个整数t (1≤t≤10^4) — 测试用例的数量。
每个案例的第一行包含一个整数n (1≤n≤2×10^5) — 树中顶点的数量。
接下来的n-1行每行包含两个整数u和v (1≤u,v≤n, u≠v) — 由边连接的顶点的索引。
保证所有案例的n之和不超过2×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
```**题意翻译** 给定一棵树，1号为根。你可以调整一个点的儿子顺序，问这棵树是否有可能对称。 一棵树对称，如果根满足： - 根最左边的儿子的子树与最右边的儿子的子树成镜像。 - 根左边第二个的儿子的子树与右边第二个儿子的子树成镜像。 ........ - 如果儿子个数为奇数，那么中间的儿子的子树也满足对称。 **题目描述** Kid得到了一棵有n个顶点的树，1号顶点为根。因为他非常喜欢对称的物体，所以他想知道这棵树是否对称。 在这个图中的树是不对称的。形式上，如果存在一个孩子的顺序使得： - 根的最左边的孩子的子树是根的最右边孩子的子树的镜像； - 根的第二个左边的孩子的子树是根的第二个右边的孩子的子树的镜像； - ... - 如果根的孩子数是奇数，那么根的中间孩子的子树也应该是对称的。 **输入输出格式** **输入格式** 输入数据的第一行包含单个整数t (1≤t≤10^4) — 测试用例的数量。 每个案例的第一行包含一个整数n (1≤n≤2×10^5) — 树中顶点的数量。 接下来的n-1行每行包含两个整数u和v (1≤u,v≤n, u≠v) — 由边连接的顶点的索引。 保证所有案例的n之和不超过2×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 ```
给定一棵树，1号为根。你可以调整一个点的儿子顺序，问这棵树是否有可能对称。
一棵树对称，如果根满足：
- 根最左边的儿子的子树与最右边的儿子的子树成镜像。
- 根左边第二个的儿子的子树与右边第二个儿子的子树成镜像。
........
- 如果儿子个数为奇数，那么中间的儿子的子树也满足对称。
**题目描述**
Kid得到了一棵有n个顶点的树，1号顶点为根。因为他非常喜欢对称的物体，所以他想知道这棵树是否对称。
在这个图中的树是不对称的。形式上，如果存在一个孩子的顺序使得：
- 根的最左边的孩子的子树是根的最右边孩子的子树的镜像；
- 根的第二个左边的孩子的子树是根的第二个右边的孩子的子树的镜像；
- ...
- 如果根的孩子数是奇数，那么根的中间孩子的子树也应该是对称的。
**输入输出格式**
**输入格式**
输入数据的第一行包含单个整数t (1≤t≤10^4) — 测试用例的数量。
每个案例的第一行包含一个整数n (1≤n≤2×10^5) — 树中顶点的数量。
接下来的n-1行每行包含两个整数u和v (1≤u,v≤n, u≠v) — 由边连接的顶点的索引。
保证所有案例的n之和不超过2×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
```**题意翻译** 给定一棵树，1号为根。你可以调整一个点的儿子顺序，问这棵树是否有可能对称。 一棵树对称，如果根满足： - 根最左边的儿子的子树与最右边的儿子的子树成镜像。 - 根左边第二个的儿子的子树与右边第二个儿子的子树成镜像。 ........ - 如果儿子个数为奇数，那么中间的儿子的子树也满足对称。 **题目描述** Kid得到了一棵有n个顶点的树，1号顶点为根。因为他非常喜欢对称的物体，所以他想知道这棵树是否对称。 在这个图中的树是不对称的。形式上，如果存在一个孩子的顺序使得： - 根的最左边的孩子的子树是根的最右边孩子的子树的镜像； - 根的第二个左边的孩子的子树是根的第二个右边的孩子的子树的镜像； - ... - 如果根的孩子数是奇数，那么根的中间孩子的子树也应该是对称的。 **输入输出格式** **输入格式** 输入数据的第一行包含单个整数t (1≤t≤10^4) — 测试用例的数量。 每个案例的第一行包含一个整数n (1≤n≤2×10^5) — 树中顶点的数量。 接下来的n-1行每行包含两个整数u和v (1≤u,v≤n, u≠v) — 由边连接的顶点的索引。 保证所有案例的n之和不超过2×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 ```