题目原文如下：

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 代码的逻辑？感激不尽！

大佬有話說 (0)