There are \(N\) cities numbered \(1,2, \ldots, N\) and \((N-1)\) bi-directional roads in a country. No two cities have multiple roads between them. All roads connect two different cities. For all pairs of cities, there is a path from one to another.
The road between cities \(u_i\)and \(v_i\) has cost \(w_i\) assigned to it which means one has to pay \(w_i\) unit of money in order to go from city \(u_i\) to \(v_i\) or vice-versa. The cost of traveling from one city to another is the sum of costs assigned to the roads that are on the simple path between these cities.
You are given \(Q\) queries. For the \(i^{th}\) query, you will be provided a set of \(k_i\) cities {\(a_1, a_2, \ldots, a_k\)}.
You have to find any city in the country such that the maximum cost from this city to the set of cities is minimum. Formally, let the set of traveling costs from city \(x\) to the given set of cities be {\(d_{1x}, d_{2x}, \ldots, d_{kx}\)}. You are required to find a city \(x\) for which \(max(d_{1x}, d_{2x}, \ldots, d_{kx})\) is minimum. If there are multiple such cities, print the city with the lowest number.
Input format
- The first line of input contains two integers \(N\) the number of cities and \(Q\) the number of queries.
- Next \(N-1\) lines contain three integers \(u_i, v_i\) and \(w_i\), meaning there is a road connection cities \(u_i\) and \(v_i\) which has cost \(w_i\) assigned to it.
- Each of the next \(Q\) lines has the following format:
- The \(i^{th}\) line starts with a number \(k_i (1 \leq k_i \leq 500)\) the number of cities in the set, then follows \(k_i\) cities {\(a_1, a_2, \ldots, a_k\)}.
Note: Sum of \(k_i\) over all queries does not exceed \(5000\).
Output format
For each query, print a single line containing the answer to the query. If there are multiple answers, print the one with the smallest number.
Constraints
\(1 \leq N \leq 2 \times 10^5\)
\(1 \leq Q \leq 5000\)
\(1 \leq (u_i, v_i) \leq N\)
\(1 \leq w_i \leq 10^9\)
\(\sum k_i \leq 5000\) and \(1 \leq k_i \leq 500\)
\(1 \leq a_i \leq N\)
5 2 1 2 5 2 3 3 4 1 2 4 5 7 3 2 3 5 2 4 5
1 4
For the first query, the cities in the given set are {\(2, 3, 5\)}.
From city \(1\), the cost of travelling to cities \(2, 3\) and \(5\) are \(5, 8, 9\) respectively. For \(1\), we have \(max(5, 8, 9) = 9\).
From city \(2\), the cost of travelling to cities \(2, 3\) and \(5\) are \(0, 3, 14\) respectively. For \(2\), we have \(max(0, 3, 14) = 14\).
From city \(3\), the cost of travelling to cities \(2, 3\) and \(5\) are \(3, 0, 17\) respectively. For \(3\), we have \(max(3, 0, 17) = 17\).
From city \(4\), the cost of travelling to cities \(2, 3\) and \(5\) are \(7, 10, 7\) respectively. For \(4\), we have \(max(7, 10, 7) = 10\).
From city \(5\), the cost of travelling to cities \(2, 3\) and \(5\) are \(14, 17, 0\) respectively. For \(5\), we have \(max(14, 17, 0) = 17\).
So, the answer for the first query will be \(1\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor