Building New Channels Over a Tree Network

In this problem, the country’s road network is modeled as a tree with unit edge weights, and cities are located at the vertices. The cost of building a new channel between any two cities a and b is defined as the length of the shortest path between a and b in the tree (i.e. the number of edges on the unique path between a and b, which can be written in LaTeX as $d(a,b)$).

For each plan, you are given a set of $k$ distinct vertices. For every pair of these vertices, a new channel is constructed, so a total of (\binom{k}{2}) channels are built. Your task is to compute the following for each plan:

1. The sum of the construction costs of all the new channels.
2. The minimum construction cost among all the new channels.
3. The maximum construction cost among all the new channels.

If $k < 2$, output 0 for all three values.

inputFormat

The input begins with an integer $n$ $(1 \le n \le 10^5)$, the number of vertices in the tree. Then follow $n-1$ lines each containing two integers $u$ and $v$, describing an edge between vertices $u$ and $v$. It is guaranteed that the given graph is a tree with unit edge weights.

Next, an integer $Q$ is given, representing the number of plans. Each plan is described as follows:

• An integer $k$ (number of selected vertices).
• A line with $k$ space-separated integers indicating the selected vertices.

Note: The vertices are 1-indexed.

outputFormat

For each plan, output three space-separated integers on a new line: the total cost of building channels, the minimum channel cost, and the maximum channel cost. If there is no channel (i.e. when $k < 2$), output "0 0 0".

sample

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

3 3 3