Minimum distance

2

1 votes
Algorithms, Approved, Graphs, Hard
Problem

You are given a tree and q queries. Each query consists of \(k_i\) vertices: \(v_{i,1}\), ..., \(v_{i,k}\).

Let \(f_i(u)\) be the minimum between distances from u to each \(v_{i,j}\), for \(1 \le j \le k_i\). For each query you have to find value of \(\max\limits_{u \in V}f_i(u)\).

Input Format:
First line of input contains n and q (\(2 \leq n \leq 2 \cdot 10^5\); \(1 \leq q \leq 10^5\)).

Then follow \(n - 1\) lines with edges descriptions. The i-th of them contains integers \(a_i\) and \(b_i\) (\(1 \leq a_i, b_i \leq n\)) — describing the edge connecting vertices \(a_i\) and \(b_i\).

Then follow q lines with query descriptions. The i-th of them contains integer \(k_i\) (\(1 \leq k_i \leq 5\)) followed by \(k_i\) integers \(v_{i, j}\) (\(1 \leq v_{i, j} \leq n\)).

Note that \(v_{i,j}\) are not necessarily distinct in a single query.

Output Format:
Print q lines. The i-th of them should contain a single integer — maximum of \(f_i(u)\) among all vertices in the tree.

Time Limit: 2
Memory Limit: 512
Source Limit:
Explanation
  • In the first query: \(f(1) = 0\), \(f(2) = 1\), \(f(3) = 1\), \(f(4) = 2\), \(f(5) = 2\)
  • In the second query: \(f(1) = 0\), \(f(2) = 0\), \(f(3) = 1\), \(f(4) = 1\), \(f(5) = 1\)
Editor Image

?