← 返回题目列表

Codeforces · 391/E2

E2. 三棵树

中文机器翻译题面 查看原题

该问题由两个子问题组成:解决子问题 E1,您将获得 11 分,解决子问题 E2,您将获得 13 分。

树是不包含环的无向连通图。未加权树中两个节点之间的距离是从一个节点到另一个节点必须遍历的最小边数。

给你 3 棵树,必须通过在这些树之间添加两条边将它们合并成一棵树。每条边都可以连接两棵树中的任意一对节点。连接树后,应计算联合树中所有无序节点对之间的距离。这些距离之和的最大可能值是多少?

输入

第一行包含三个空格分隔的整数 n1、n2、n3 — 分别是第一、第二和第三棵树中的顶点数。以下 n1 - 1 行描述第一棵树。这些行中的每一行都描述第一棵树中的一条边,并包含一对由单个空格分隔的整数 - 由边连接的顶点的数字标签。接下来的 n2 - 1 行以相同的方式描述第二棵树,之后的 n3 - 1 行类似地描述第三棵树。每棵树中的顶点都用从 1 开始的连续整数进行编号。

该问题由两个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。

- 在子问题 E1(11 个点)中,每棵树中的顶点数将在 1 到 1000 之间(包含 1 和 1000)。
- 在子问题 E2(13 个点)中,每棵树中的顶点数将在 1 到 100000 之间(包含 1 和 100000)。

输出

打印一个整数——联合树中所有节点对之间距离的最大可能总和。

示例

输入 #1

2 2 3
1 2
1 2
1 2
2 3

输出 #1

56

输入 #2

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

输出 #2

151

注意

考虑第一个测试用例。有两棵树由两个节点组成,一棵树由三个节点组成。如果树以 7 个顶点的单链连接,则可以获得最大可能的答案。

在第二个测试用例中,为获得最大答案而可能选择的新边如下:

- 将第一棵树的节点 3 连接到第二棵树的节点 1;
- 将第三棵树的节点 2 连接到第二棵树的节点 1。