CF391E2.Three Trees

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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.

输入格式

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.

输入输出样例

输入#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
```

说明/提示

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.

首页