DMOPC '19 Contest 2 P6 - Two Roots

View as PDF

Submit solution

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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, \ldots , x_k if the tree were rooted at A and the lowest common ancestor of x_1, x_2, \ldots , x_k if the tree were rooted at B. The lowest common ancestor of x_1, x_2, \ldots , x_k is defined as the node furthest from the root such that it contains each of x_1, x_2, \ldots , 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.


In 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 will contain 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, \ldots , 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.