#P2368. Modern Art Plagiarism 树同构

    ID: 1411 传统题 1000ms 128MiB 尝试: 48 已通过: 15 难度: 7 上传者: 标签>CF2200提高树形 DP二分图建模Kuhn 算法暴力枚举googlecodejam

Modern Art Plagiarism 树同构

题目描述

定义树 AA 与 BB 同构,当且仅当树 AA 的顶点经过一定的重新标号,树 AA 的顶点集合边集完全与树 BB 一一对应。

Your Task:给定两棵树 T1T_1 与 T2T_2,判断是否存在 T1T_1 的子树 T3T_3,使得 T3T_3 与 T2T_2 同构。

(注:这里的子树指的是树上的一个联通子图)

输入格式

本题有多组数据。

第一行 TT 表示数据组数。

对于每组数据,第一行 nn 表示 T1T_1 的点数。

接下来 n−1n-1 行每行两个整数 a,ba,b 描述 T1T_1 的一条边。

接下来一行 mm 表示 T2T_2 的点数。

再接下来 m−1m-1 行每行两个整数 a,ba,b 描述 T2T_2 的一条边。

输出格式

对于每组数据,在一行中输出 YES 表示存在 T3T_3 与 T2T_2 同构,NO 表示不存在。

样例输入

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

样例输出

NO
YES

样例说明

第一组数据中 T2T_2 的点 11 度数为 33,而 T1T_1是一条链,没有度数为 33 的点,显然 NO。

第二组数据中 T2T_2 是一条 44 个点的链,与 T1T_1 中的 2−1−4−52-1-4-5 同构。

数据规模与约定

对于 100%100\% 的数据:T≤10,1≤m≤n≤100T\le 10,1\le m\le n\le 100。

题目来源

google code jam 2008 APAC Onsites