题意理解

• 树 $A$ 有 $N$ 个节点。
• 树 $B$ 有 $N+1$ 个节点。
• 树 $B$ 是由树 $A$ 增加一个叶子节点（并可能重新编号）得到的。
• 我们要找出树 $B$ 中多出来的那个叶节点。

注意：

• 增加一个叶子节点意味着在树 $A$ 的某个节点上连一个新节点（新节点度为 $1$）。
• 在树 $B$ 中，这个新节点是叶子（度 = 1），并且删除它后，剩下的图应该与树 $A$ 同构（节点编号可以不同，但结构相同）。

关键思路

1. 度数分析
   在树 $B$ 中，多出来的那个叶子节点在树 $A$ 中不存在，所以它的度数为 $1$。
   但是树 $B$ 中可能有多个度数为 $1$ 的节点（叶子），不能仅凭度数为 $1$ 就确定。

2. 同构判断
   如果我们从树 $B$ 中删除一个叶子节点 $x$（以及它连的边），剩下的图应该是一棵 $N$ 个节点的树，并且与树 $A$ 同构。

3. 直接做法复杂度
   对树 $B$ 的每个叶子节点，删除它，检查剩下的树是否与 $A$ 同构，这样最坏 $O(N^2)$，不可行。

4. 优化思路
   考虑树哈希：

   • 对树 $A$ 计算一个哈希值（例如用 AHU 哈希或子树大小哈希等，保证同构树哈希相同，不同构大概率不同）。
   • 对树 $B$，如果删除一个叶子 $v$，我们只需要计算删除 $v$ 后树的哈希值，看是否等于树 $A$ 的哈希值。
   • 删除叶子 $v$ 后，树 $B$ 的哈希值可以通过动态树哈希或预处理树哈希后 $O(1)$ 或 $O(\deg)$ 计算。

5. 具体步骤

   • 选一个树哈希方法（例如用质数权重，子树哈希 = 1 + $sum(prime[size_child] * hash(child))）$。
   • 先以任意根对树 $A$ 做 DFS 计算哈希。
   • 对树 $B$，任选一个根（如 1）做 DFS 计算哈希，并记录每个节点作为根时整棵树的哈希（换根 DP）。
   • 对树 $B$ 的每个叶子节点 $v$，它的父节点是 $p$，删除 $v$ 后，树 $B$ 的根可以设为 $p$（因为删除叶子不影响其他部分结构），我们得到以 $p$ 为根时树 $B$ 去掉 $v$ 后的哈希值（其实就是 $p$ 在树 $B$ 中少一个子树的哈希值），比较它和树 $A$ 的哈希值。
   • 如果匹配，说明 $v$ 是多余叶子。

算法步骤

1. 读入 $N$，读入树 $A$ 和树 $B$ 的边。
2. 选择一个哈希方法（例如用质数表对应节点度数或子树大小）。
3. 对树 $A$ 计算哈希 $H_A$（以 1 为根）。
4. 对树 $B$ 做 DFS 计算哈希，并做换根 DP 得到每个节点为根时的哈希值。
5. 遍历树 $B$ 中所有叶子节点（度 = 1），检查删除它后剩余树的哈希是否等于 $H_A$。
6. 输出符合条件的最小编号。

样例验证

样例：

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

树 $A$: 1-2, 2-3, 1-4, 1-5
树 $B$: 1-2, 2-3, 3-4, 4-5, 3-6

树 $B$ 的叶子有：1, 5, 6

• 删除 1：剩下 2-3-4-5 和 3-6，与 $A$ 同构
• 删除 5：剩下 1-2-3-4 和 3-6，与 $A$ 不同构
• 删除 6：剩下 1-2-3-4-5（一条链），与 $A$ 不同构 删除叶子 1 后，树 $B$ 剩余结构是： 2-3-4-5 和 3-6（即节点 2 连 3，3 连 4 和 6，4 连 5），这其实和 $A$ 同构 $A$ 的结构：1 连 2,4,5；2 连 3。
  把 $A$ 的 1 映射到 $B$ 的 3，$A$ 的 2 映射到 $B$ 的 2，$A$ 的 3 映射到 $B$ 的 4，$A$ 的 4 映射到 $B$ 的 6，$A$ 的 5 映射到 $B$ 的 5，确实同构。
  所以删除 1 后是同构的，因此 1 是多余叶子。

复杂度

• 树哈希 + 换根 DP：$O(N)$
• 检查每个叶子：$O(N)$

总结：
这道题的核心是树同构判断结，通过树哈希和换根 DP 来高效求解。