King's Castle Communication Cost

In ancient times, a king ruled over n villages which were connected by n-1 roads forming a tree structure. The original castle of the king was located at village 1. Later, as the king's son neared adulthood, he started building his own castles at some villages (one castle per village) in a given order. Each castle needs to communicate with every other castle. To do so, every day each castle sends a carrier pigeon to every other castle. A pigeon consumes 1 gram of grain per kilometer flown.

Define \(dis(x,y)\) as the grain cost (in grams) for sending a message from castle at village \(x\) to castle at village \(y\) (i.e. the distance between \(x\) and \(y\)). For a given sequence of castle constructions (the first castle is always at village 1), after each castle is built, compute the minimum total grain cost that will ensure full communication among all built castles. Formally, after the \(i\)th castle is constructed, you are to output:

[ T_i = \sum_{x=1}^{i} \sum_{y=1}^{i} dis(x,y)]

Note that \(dis(x,x)=0\). Also, since the communication is bidirectional, each distinct pair \(\{x,y\}\) contributes twice to the sum (i.e. once for each direction). Since the tree is unweighted (each road is 1 km), the distance between any two villages is simply the number of roads in the unique path connecting them.

inputFormat

The first line contains a single integer n (\(2 \leq n \leq 1000\)), the number of villages. The next n-1 lines each contain two integers u and v indicating that there is a bidirectional road between villages u and v (each road has length 1 km).

The following line contains a single integer m (\(1 \leq m \leq n\)), representing the total number of castles. Initially there is already a castle at village 1. The next m-1 lines each contain one integer indicating the village in which a new castle is built, in the order of construction.

outputFormat

Output m lines. The \(i\)th line should contain the total minimal communication cost (in grams) after the construction of the first \(i\) castles, i.e., \[ T_i = \sum_{x=1}^{i} \sum_{y=1}^{i} dis(x,y)\]

sample

5
1 2
2 3
2 4
1 5
3
2
4

0
2
8