Guard Tower Energy Minimization

In Lost Light City there are \(N\) islands connected by \(N-1\) space channels. Each channel between two islands \(u\) and \(v\) has an energy cost \(w\). As the guardian, Yue LingShuang can deploy a guard tower on any island (at most one per island) in order to transmit messages via special spatial waves to every island that has residents. However, all towers deployed at the same time must form a chain – that is, they must lie along a simple path in the tree.

Moreover, when an island is hit by a space storm, its residents evacuate; the corresponding tower then does not need to transmit messages. Once the storm subsides and residents return, message transmission must resume. Since the transmission from any tower to an island consumes energy equal to the sum of the energy costs along the unique path connecting their islands (and if the island is the same as that of the tower the cost is \(0\)), each tower independently transmits to every island with residents.

The overall energy consumption is the sum over all towers of the cost needed to send messages to all islands that currently have residents. Formally, if a set \(T\) of islands is selected (which forms a simple path of the tree) as sites for towers and \(A\) is the set of islands with residents, then the energy consumption is defined as:

[ E(T)=\sum_{t\in T}\sum_{a\in A} d(t,a), ]

Since deploying more than one tower always increases the cost, it is always optimal to deploy just one tower. Therefore, the problem reduces to: Given the tree and a subset \(A\) of active (non‐stormed) islands, choose an island \(v\) to deploy a single tower so that the energy consumption \(\sum_{a\in A} d(v,a)\) is minimized.

You are given the structure of Lost Light City and several queries. Each query gives a set of islands where residents are present. For each query, compute the minimum total energy consumption.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(N\) \((1 \le N \le 10^5)\), the number of islands.

Then \(N-1\) lines follow, each containing three integers \(u\), \(v\) and \(w\) \((1 \le u,v \le N, 1 \le w \le 10^5)\) representing a bidirectional space channel between islands \(u\) and \(v\) with energy cost \(w\).

The next line contains an integer \(Q\) \((1 \le Q \le 10)\), the number of queries.

Each query consists of a line beginning with an integer \(k\) \((0 \le k \le N)\) representing the number of islands that are active (i.e. not struck by a storm), followed by \(k\) distinct integers denoting the indices of these islands.

If \(k=0\), then there are no islands with residents and the answer is \(0\).

outputFormat

For each query, output a single integer, the minimum total energy consumption needed to transmit messages to all active islands.

sample

3
1 2 1
2 3 2
1
2 1 3

3

</p>