CF391E1.Three Trees

This problem consists of two subproblems: for solving subproblem E1 you will receive 11 points, and for solving subproblem E2 you will receive 13 points.

A tree is an undirected connected graph containing no cycles. The distance between two nodes in an unweighted tree is the minimum number of edges that have to be traversed to get from one node to another.

You are given 3 trees that have to be united into a single tree by adding two edges between these trees. Each of these edges can connect any pair of nodes from two trees. After the trees are connected, the distances between all unordered pairs of nodes in the united tree should be computed. What is the maximum possible value of the sum of these distances?

本题包含两个子问题：解决子问题 E1 可获得 11 分，解决子问题 E2 可获得 13 分。

树（tree）是一个无向连通图，且其中不含环。在无权树中，两个节点之间的距离定义为从一个节点到达另一个节点所需经过的最少边数。

给定 3 棵树，你需要通过添加两条边将它们合并成一棵单一的树。每条新增的边可以连接任意两棵不同树中的任意两个节点。合并后，需计算新树中所有无序节点对之间的距离，并求这些距离之和的最大可能值。

The first line contains three space-separated integers _n_1, _n_2, _n_3 — the number of vertices in the first, second, and third trees, respectively. The following _n_1 - 1 lines describe the first tree. Each of these lines describes an edge in the first tree and contains a pair of integers separated by a single space — the numeric labels of vertices connected by the edge. The following _n_2 - 1 lines describe the second tree in the same fashion, and the _n_3 - 1 lines after that similarly describe the third tree. The vertices in each tree are numbered with consecutive integers starting with 1.

The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

• In subproblem E1 (11 points), the number of vertices in each tree will be between 1 and 1000, inclusive.
• In subproblem E2 (13 points), the number of vertices in each tree will be between 1 and 100000, inclusive.

第一行包含三个以空格分隔的整数 $n_1$、$n_2$、$n_3$ —— 分别表示第一棵、第二棵和第三棵树的顶点数量。接下来的 $n_1 - 1$ 行描述第一棵树；每行描述第一棵树中的一条边，包含一对以单个空格分隔的整数 —— 即该边所连接的两个顶点的编号。随后的 $n_2 - 1$ 行以相同方式描述第二棵树，再之后的 $n_3 - 1$ 行同样方式描述第三棵树。每棵树中的顶点均用从 1 开始的连续整数编号。

本题包含两个子问题。各子问题对输入具有不同的约束条件。正确提交某个子问题可获得相应分数。子问题的描述如下：

• 子问题 E1（11 分）：每棵树的顶点数在 $1$ 到 $1000$（含）之间。
• 子问题 E2（13 分）：每棵树的顶点数在 $1$ 到 $100000$（含）之间。

Print a single integer number — the maximum possible sum of distances between all pairs of nodes in the united tree.

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

Consider the first test case. There are two trees composed of two nodes, and one tree with three nodes. The maximum possible answer is obtained if the trees are connected in a single chain of 7 vertices.

In the second test case, a possible choice of new edges to obtain the maximum answer is the following:

• Connect node 3 from the first tree to node 1 from the second tree;
• Connect node 2 from the third tree to node 1 from the second tree.

考虑第一个测试用例。其中包含两棵由两个节点组成的树，以及一棵由三个节点组成的树。若将这些树连接成一条包含 7 个顶点的单一链，则可得到最大的可能答案。

在第二个测试用例中，一种能获得最大答案的新边选择方案如下：

• 将第一棵树的节点 3 与第二棵树的节点 1 相连；
• 将第三棵树的节点 2 与第二棵树的节点 1 相连。