Minimum distance
Tag(s):

Algorithms, Graph, Hard

Problem
Editorial
Analytics

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.

SAMPLE INPUT
5 2
1 2
1 3
2 4
2 5
1 1
2 1 2
SAMPLE OUTPUT
2
1
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$
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...

Contributor

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Dynamic Programming
• Math > Number Theory
• Algorithms > Graphs
• Data Structures > Advanced Data Structures