Tree Isomorphism II

题目描述

给定两棵（无根）树，你的任务是判断它们是否同构，即是否存在一种绘制方式使得它们看起来相同。

输入格式

第一行输入为一个整数 $t$：测试用例的数量。接下来有 $t$ 个测试，每个测试描述如下： 第一行有一个整数 $n$：两棵树的节点数。节点编号为 $1,2,\dots,n$。 然后有 $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

YES
YES

提示

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

标签: CSES1701|高级图论问题

来源

CSES1701|高级图论问题