Tree Isomorphism I

题目描述

给定两棵有根树，你的任务是判断它们是否同构，也就是说，是否可以把它们画成看起来相同。

输入格式

第一行输入一个整数 t：测试用例的数量。接下来有 t 个测试，每个测试描述如下： 第一行有一个整数 n：两棵树的节点数。节点编号为 1,2,$\dots$,n，且节点 1 为根。 然后有 n-1 行描述第一棵树的边，最后有 n-1 行描述第二棵树的边。

输出格式

对于每个测试，若两棵树同构则输出 "YES"，否则输出 "NO"。

2
3
1 2
2 3
1 2
1 3
3
1 2
2 3
1 3
3 2

NO
YES

提示

$1 \le t \le 1000$ $2 \le n \le 10^5$ $n$

标签: CSES1700|高级图论问题

来源

CSES1700|高级图论问题