SP17789 SPACEBRG - Space Bridges

**空间桥梁** 在遥远的星系中，银河帝国与反叛军联盟爆发了一场大战。在这样的战争时期，空间桥梁成为了重要的战略资源，因为它们可以瞬间将物资或军队从一个空间区域调度到另一个。每个空间区域由多个扇区构成，这些扇区通过空间道路连接，从一个扇区到另一个扇区恰好有一条路径。需要注意的是，空间道路不同于空间桥梁。 帝国的两个区域的扇区排列方式已经完成。为了确认这个布局的强度是否足够大，帝国的最高指挥官要求你——帝国的顶尖程序员，来计算这两个区域的总强度。 两个区域之间可以通过仅一条空间桥梁连接，即从一个区域的一个扇区连接到另一个区域的一个扇区。空间桥梁的强度值定义为从第一区域的任何扇区到第二区域的任何扇区所需的最大路径长度，这条路径至多使用一次空间道路或空间桥梁。两个区域的总强度是所有可能的空间桥梁连接强度的总和。 给定两个空间区域的扇区排列，计算它们的总强度。要注意，如果结果不如预期，帝国的指挥官可能会对你施展“原力掐喉”——祝您好运！

输入以一个整数 $T$ 开始，表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别是两个空间区域中的扇区数量。接下来 $n-1$ 行描述第一个区域的扇区排列。每行包含两个整数 $u$ 和 $v$，表示扇区 $u$ 和扇区 $v$ 之间由一条空间道路连接。保证这种安排使得从一个扇区到另一个恰好有一条路径，并且没有重复的空间道路。随后 $m-1$ 行为第二个区域的扇区排列，与第一个区域相似。

对于每个测试用例，输出一行，格式为“Case X: Y”，其中 X 是测试用例编号，Y 是两个空间区域的总强度。

- $1 \leq T \leq 5$ - $1 \leq n, m \leq 10^5$ **提示**：考量到数据集量大，请务必使用高效的输入输出方式。 **题目提供者：Aninda Majumder** **特别感谢：Momontho Mashak Monmoy, Nafis Sadique, Ahmad Faiyaz** **本翻译由 AI 自动生成**