DMOPC '19 Contest 2 P6 - Two Roots

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 128M

Problem types

You are given a tree consisting of N nodes. Bob has chosen two distinct nodes, A and B, which you are to determine. You can ask up to Q queries of the form: k\ x_1\ x_2 \dots x_k and Bob will tell you the distance between the lowest common ancestor of x_1, x_2, \dots, x_k if the tree were rooted at A and the lowest common ancestor of x_1, x_2, \dots, x_k if the tree were rooted at B. The lowest common ancestor of x_1, x_2, \dots, x_k is defined as the node furthest from the root such that it contains each of x_1, x_2, \dots, x_k in its subtree. The distance between two nodes a and b is defined as the number of edges on the unique shortest path from a to b.

If your program exceeds the query limit or makes an invalid query, the interactor will print -1. Make sure your program terminates immediately after reading -1 or you may get an arbitrary verdict.

Note: the interactor will take up approximately 1 second of execution time.


For all subtasks:
2 \le N \le 1000

Subtask 1 [30%]

Q = 1000

Subtask 2 [20%]

The degree of each node is at most 2.

Q = 128

Subtask 3 [50%]

Q = 40

Input Specification

The first line of input contains one integer, N.
The next N-1 lines of input contain two space-separated integers, x_i y_i, indicating that there is an edge between x_i to y_i.
The next i-th line contains one integer which is Bob's answer to your i-th query.

Output Specification

For a query, print ? k x_1 x_2 ... x_k on a new line where k is the number of nodes you want to query and x_1, x_2, \dots, x_k are the nodes.
When you have the answer, print ! A B where A and B are the nodes Bob chose in any order.

Sample Interaction

>>> denotes your program's output. Don't actually print this out.

1 2
1 3
1 8
2 7
3 4
3 5
3 6
>>> ? 2 2 5
>>> ? 3 4 1 6
>>> ? 2 8 4
>>> ! 2 5


There are no comments at the moment.