An Animal Contest 2 P6 - Koala Transport System

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Java 2.0s
Python 2.0s
Memory limit: 256M
Python 512M

Problem types

Lately, the koalas have noticed that their feeding grounds are too far away from their home so they have decided to find a better way to move between their destinations. Lucky for them, you have a bunch of teleporters lying around, so they hire you to fix their problem!

The koalas live in a forest of N connected trees, numbered from 1 to N, joined by N-1 branches that can be crossed in either direction in 1 minute; each tree is a possible feeding ground. The koalas' home is tree 1. On each of the next Q days, the koalas will have a new set of X distinct feeding grounds, with the i^{th} feeding ground designated as x_i.

A teleportation plan for the koalas will be built daily. To do so, we will first choose any tree v. Then, on all the trees on the unique simple path from tree 1 to tree v, we will install a teleporter; a teleporter allows for instant travel to any other teleporter. Note that teleporters only last for one day and a plan must be redesigned every day.

Each day, koalas populate all feeding grounds designated for that day, and every evening, all koalas need to return home. Among all possible teleportation plans, you are to find one that allows all the koalas to return to tree 1 using the minimum total time t and report this number to the chief koala!

For this problem, Python users are recommended to use PyPy over CPython.


For this problem, you will NOT be required to pass the sample cases in order to receive points.

1 \le N \le 2 \cdot 10^5

1 \le Q \le N

1 \le X, x_i \le N

For each day, all x_i are distinct.

The sum of X over all days is guaranteed to be less than or equal to N.

Subtask 1 [5%]

1 \le N \le 2 \cdot 10^3

Subtask 2 [15%]

Q = 1

Subtask 3 [80%]

No additional constraints.

Input Specification

The first line contains two space-separated integers N and Q.

The next N-1 lines each contain 2 integers u and v, indicating a bidirectional branch between trees u and v.

2 \cdot Q lines follow, with 2 lines for each day. The first line for each day contains X, followed by X integers x_i on the next line, representing the designated feeding grounds for day i.

Output Specification

Output Q lines, the i^{th} of which contains the minimum time t for the i^{th} day.

Sample Input 1

6 2
1 2
2 3
1 4
4 5
2 6
3 5 6
1 2 6

Sample Output 1


Explanation for Sample 1

For the first day, the optimal v is 6, and the teleporters will be installed on trees 1, 2, and 6. Since tree 6 is already on the path, its distance is 0. Tree 3 is 1 branch away from its closest teleporter (tree 2) and tree 5 is 2 branches away from its closest teleporter at tree 1. Therefore the answer is 0+1+2 = 3 minutes.

For the second day, we again choose v = 6. Since teleporters are installed on all feeding grounds, the answer is 0.

Sample Input 2

6 2
5 1
1 6
6 3
3 4
4 2
5 6
1 2 3

Sample Output 2



There are no comments at the moment.