P17773 挑战 NPC IV

在计算机科学中，**NP 完全（NP-Complete，简称 NPC）问题**是一类兼具理论深度与求解难度的经典问题——目前尚未找到它们的多项式时间算法，但一旦其中任何一个问题被攻克，所有的 NP 问题都将迎刃而解。 热衷于算法研究的小 W 一直梦想着挑战 NPC 问题。他了解到，图论中著名的“最大公共诱导子图问题”正是经典的 NPC 问题。面对一般图上难以逾越的复杂度鸿沟，小 W 决定退一步，先从结构更为优美的树入手，研究树上的同构连通子图问题。 具体而言，给定两棵均包含 $n$ 个节点的无根树 $T_1$ 和 $T_2$，两棵树的节点均分别编号为 $1 \sim n$。小 W 希望在 $T_1$ 中选出一个非空节点子集 $V_1$，并在 $T_2$ 中选出一个非空节点子集 $V_2$，同时保留各自集合内部节点在原树中的所有原有边，从而分别导出两个子图 $G_1$ 和 $G_2$。 小 W 要求导出的两个子图 $G_1, G_2$ 必须同时满足： 1. 连通性：$G_1$ 和 $G_2$ 均为连通图（特别地，仅包含 $1$ 个节点的图也视为连通）。 2. 同构性：$G_1$ 与 $G_2$ 同构。即存在一个从 $V_1$ 到 $V_2$ 的双射（一一对应关系）$f: V_1 \to V_2$，使得对于任意 $u, v \in V_1$，$u$ 与 $v$ 在 $G_1$ 中有边相连，当且仅当 $f(u)$ 与 $f(v)$ 在 $G_2$ 中有边相连。注意：**相互对应的节点 $u$ 和 $f(u)$ 不要求编号相同**。 现在，小 W 将这个简化后的问题交给了你：请计算满足上述要求的同构连通子图最多可以包含多少个节点（即求 $\vert V_1\vert$ 的最大值）？

从标准输入读入数据。 第一行包含一个正整数 $n$，表示每棵树的节点数量。 接下来 $n - 1$ 行，每行包含两个正整数 $u, v$，表示树 $T_1$ 中的一条无向边 $(u, v)$。 接下来 $n - 1$ 行，每行包含两个正整数 $u, v$，表示树 $T_2$ 中的一条无向边 $(u, v)$。

输出到标准输出。 输出一行一个正整数，表示选出的同构连通子图的最大节点数。

### 样例 1 解释 在 $T_1$ 中选择节点集合 $V_1 = \{1, 2, 3\}$，在 $T_2$ 中选择节点集合 $V_2 = \{1, 2, 3\}$。将 $V_1$ 中的节点 $1, 2, 3$ 依次对应到 $V_2$ 中的节点 $2, 1, 3$，导出的两个子图均为包含 $3$ 个节点的链，满足连通且同构。 由于 $T_1$ 本身是一条链，其任意连通子图也必然是一条链；而菊花图 $T_2$ 中最长的链仅包含 $3$ 个节点，因此无法选出节点数超过 $3$ 的同构连通子图。 ### 样例 2 见题目附件中的 `npc/npc2.in` 与 `npc/npc2.ans`。 该样例满足子任务 $1$ 的约束条件。 ### 样例 3 见题目附件中的 `npc/npc3.in` 与 `npc/npc3.ans`。 该样例满足子任务 $4$ 的约束条件。 ### 样例 4 见题目附件中的 `npc/npc4.in` 与 `npc/npc4.ans`。 该样例满足子任务 $7$ 的约束条件。 ### 子任务 对于全部数据，保证 $1 \le n \le 500$，每条边的两端点编号均在 $1 \sim n$ 之间，且给出的两张图均为合法的树。 本题满分为 $150$ 分，采用子任务捆绑测试。只有通过一个子任务中的全部测试点，才能获得该子任务的分数。各子任务的详细数据范围见下表。 | 子任务编号 | $n$ | 特殊性质 | 分值 | | :---: | :---: | :---: | :---: | | $1$ | $\le 10$ | 无 | $20$ | | $2$ | $\le 60$ | 无 | $25$ | | $3$ | $\le 100$ | 无 | $30$ | | $4$ | $\le 500$ | A | $20$ | | $5$ | $\le 500$ | B | $15$ | | $6$ | $\le 500$ | C | $10$ | | $7$ | $\le 500$ | 无 | $30$ | 特殊性质 A：两棵树中所有节点的度数均不超过 $3$。 特殊性质 B：存在一种最优方案，其同构映射将 $T_1$ 的节点 $1$ 对应到 $T_2$ 的节点 $1$。 特殊性质 C：保证最终答案不小于 $n - 1$。 注：树中一个节点的度数是指与该节点直接相连的边的数量。