( Problem E ) Pikachu and Champions League

★★★★★

4.5

2 votes

Algorithms, Depth First Search, Graphs, Medium

Details

Problem

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

Time Limit: 4

Memory Limit: 512

Source Limit:

Explanation

For the first query, the maximum distance is between pokemon $3$ and $4$ .
For the second query, the maximum distance is between pokemon $3$ and $5$ .
For the third query, the maximum distance is between pokemon $1$ and $4$ .
For the fourth query, the maximum distance is between pokemon $1$ and $3$ .
For the fifth query, the maximum distance is between pokemon $3$ and $4$ .

Contributers:

Pranjal Jain

Lewin Gan