All Tracks Algorithms Graphs Depth First Search Problem

Minimum distance
Tag(s):

Algorithms, 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: 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

February Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?