CF391E1 Three Trees

本题包含两个子问题：解决子问题 E1 可获得 11 分，解决子问题 E2 可获得 13 分。 一棵树是一个无向连通且无环的图。在无权树中，两个节点之间的距离是从一个节点到另一个节点所需经过的最少边数。 现在给定三棵树，需要通过添加两条边将这三棵树合并为一棵树。每条新边可以连接任意两棵树中的任意一对节点。合并后，需要计算合并后树中所有无序节点对之间的距离之和。请问，这个距离和的最大可能值是多少？

第一行包含三个用空格分隔的整数 $n_1$、$n_2$、$n_3$，分别表示第一、第二和第三棵树的节点数。接下来的 $n_1-1$ 行描述第一棵树，每行包含两个用空格分隔的整数，表示一条边连接的两个节点编号。接下来的 $n_2-1$ 行以相同方式描述第二棵树，之后的 $n_3-1$ 行同样描述第三棵树。每棵树的节点编号均为从 $1$ 开始的连续整数。 本题包含两个子问题，子问题对输入有不同的限制。你提交正确的子问题解答将获得相应分数。子问题描述如下： - 子问题 E1（11 分）：每棵树的节点数在 $1$ 到 $1000$ 之间（包含 $1$ 和 $1000$）。 - 子问题 E2（13 分）：每棵树的节点数在 $1$ 到 $100000$ 之间（包含 $1$ 和 $100000$）。

输出一个整数，表示合并后树中所有节点对之间距离之和的最大可能值。

考虑第一个测试用例。有两棵树各包含两个节点，另一棵树包含三个节点。若将三棵树连接成一个包含 7 个节点的链，则可以获得最大距离和。 在第二个测试用例中，一种可以获得最大答案的新边选择方式如下： - 将第一棵树的节点 3 与第二棵树的节点 1 相连； - 将第三棵树的节点 2 与第二棵树的节点 1 相连。 由 ChatGPT 4.1 翻译