Problem J
Joining Networks
A network of size
The transmission cost between
The transmission cost of a network is equal to the sum of the transmission cost between all unordered pair of computers.
Given network
Your task is to minimize the transmission cost of the new
network
Input
-
The first line contains an integer
- the number of computers in the network ( ). -
In the next
lines, each line contains two distinct integers and , representing a cable connecting computers and in network ( ). -
The next line contains an integer
- the number of computers in the network ( ). -
In the next
lines, each line contains two distinct integers and , representing a cable connecting computers and in network ( ).
It is guaranteed that each network is a tree.
Output
Write in one line the minimum transmission cost of the
resulting network
Sample clarification
In the first sample below, connecting computer
In the second sample below, connecting computer
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 |