Hide

# Problem JJoining Networks

A network of size $N$ contains $N$ computers connected by $N-1$ cables, so that there is exactly $1$ path between any pair of computers.

The transmission cost between $2$ computers is equal to the square of the number of cables on the path connecting the $2$ computers.

The transmission cost of a network is equal to the sum of the transmission cost between all unordered pair of computers.

Given network $A$ with $N$ computers and network $B$ with $M$ computers, the administrator wants to create a new network $C$, by adding exactly one cable connecting one computer in $A$ and one computer in $B$.

Your task is to minimize the transmission cost of the new network $C$.

## Input

• The first line contains an integer $N$ - the number of computers in the network $A$ ($1 \leq N \leq 50\, 000$).

• In the next $N-1$ lines, each line contains two distinct integers $u$ and $v$, representing a cable connecting computers $u$ and $v$ in network $A$ ($1 \leq u,v \leq N$).

• The next line contains an integer $M$ - the number of computers in the network $B$ ($1 \leq M \leq 50\, 000$).

• In the next $M-1$ lines, each line contains two distinct integers $u$ and $v$, representing a cable connecting computers $u$ and $v$ in network $B$ ($1 \leq u,v \leq M$).

It is guaranteed that each network is a tree.

## Output

Write in one line the minimum transmission cost of the resulting network $C$.

## Sample clarification

In the first sample below, connecting computer $2$ of network $A$ and computer $1$ of network $B$ will minimize the transmission cost of the network.

In the second sample below, connecting computer $4$ of network $A$ and computer $1$ of network $B$ will minimize the transmission cost of the network.

Sample Input 1 Sample Output 1
3
1 2
2 3
4
1 2
1 3
1 4

96

Sample Input 2 Sample Output 2
7
1 2
2 3
2 4
4 5
5 6
5 7
5
1 2
1 3
1 4
1 5

551

Hide