All Tracks Algorithms Graphs Depth First Search Problem

( Problem E ) Pikachu and Champions League
Tag(s):

Algorithms, Depth First Search, Graphs, Medium

Problem
Editorial
Analytics

Pikachu has already defeated so many legendary Pokemon, and is now organizing the Champions League where champions of all Conferences are going to battle for glory.

There are $$ N $$ Conferences around the world, connected by exactly $$ N-1 $$ bidirectional roads. It is always possible to reach one Conference from another.

To choose the Champion of Champions, Pikachu chooses a set $$ S $$ of Conferences. Now, each Conference champion in $$ S $$ battles with every other Conference champion in $$S$$ and for each battle, one of the champion has to travel. Pikachu wants to know the maximum distance any champion would travel to battle.

Pikachu has thought of $$ Q $$ such sets. He wants to know the maximum distance for each set so that he can choose the least tiresome set.

Constraints:

  • \(2\le N\le 500000\)
  • \(1\le Q\le 200000\)
  • It is always possible to reach one Conference from another
  • \(2\le |S|\le 500000\)
  • Sum of \(|S|\) over all Q sets is at most \(500000\)
  • All elements in S are distinct

Input format:

  • First line contains two space separated integers $$ N $$ and $$ Q $$
  • Next $$ N-1 $$ lines contain two space separated integers, $$u $$ and $$ v $$ (\(1\le u,v\le N\)), such that there is a path of length 1 between $$ u $$ and $$ v $$
  • Next $$Q$$ lines each starts with integer $$ K $$, the number of elements in set followed by $$ K $$ distinct elements.

Output format:

  • Output $$ Q $$ lines, each of which contains maximum distance for the set of Conferences.
SAMPLE INPUT
5 5
1 2
1 3
2 4
2 5
5 1 2 3 4 5
2 3 5
3 1 4 5
2 1 3
4 1 3 4 5
SAMPLE OUTPUT
3
3
2 
1
3
Explanation
  1. For the first query, the maximum distance is between pokemon $$3$$ and $$4$$.
  2. For the second query, the maximum distance is between pokemon $$3$$ and $$5$$.
  3. For the third query, the maximum distance is between pokemon $$1$$ and $$4$$.
  4. For the fourth query, the maximum distance is between pokemon $$1$$ and $$3$$.
  5. For the fifth query, the maximum distance is between pokemon $$3$$ and $$4$$.
Time Limit: 4.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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?