请教一道关于子树（图）匹配的 OJ 题

[fourstring]

题目原文如下：

---

Description

给定两棵无根树，问第一棵树是否包含第二棵树。

Input Format

此题仅有一个测试点，

多组数据，第一行为一个数表示数据组数。

对于每组数据：

第一行为 N 表示第一棵树的点数

接下来 N-1 行描述第一棵树的边

接下来一行为 M 表示第二棵树的点数

接下来 M-1 行描述第二棵树的边

Output Format

对于每组数据，若第一棵树包含第二棵树则输出 YES 否则输出 NO

Sample Input

2
5
1 2
1 3
3 4
3 5
4
1 4
2 4
3 4
4
1 2
1 3
1 4
4
1 2
2 3
3 4

Sample Output

YES
NO

Hint

n,m<=100 ； 150 组数据

---

这题和一般子树匹配问题不同的地方在于输入数据的格式，首先输入的树是无根的，实际上相当于一个图的生成树；其次两棵树之间结点的对应关系并没有给定，所以无法通过简单前序+中序遍历比较的方式来确定第一棵树是否包含了第二棵树。

从图的角度来看这似乎是一个子图匹配(Subgraph Matching)问题，查了下 Google 只找到了一些关于子图同构(Subgraph isomorphism)的资料，如 Ullmann 算法和 VF2 算法，但它们都要求两图之间结点的映射是给定的，但事实上对于本题如果能找到这样一个映射关系，剩下的也并不成为问题。

另外我还找到了本题的一份 AC 代码，不过带有明显的 OI 风格，由于我个人没有相关经验所以调试了很久也没理解这段代码的写法，链接如下：

• https://git.codingcafe.org/Contest/SJTUOJ/blob/0c4dde00abbdcc0933118e9622c66b7a76231cb5/P1314/SJTUOJ_P1314.cpp

请问是否有大佬指点一下本题的简单思路或者能大致解释一下这段 AC 代码的逻辑？感激不尽！