Hide

Problem J
Joining 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

Please log in to submit a solution to this problem

Log in