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++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, 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