Find the Special Node solution codechef

Find the Special Node solution codechef

This is an interactive task

There is a tree consisting of NN nodes. A certain node XX is marked as special, but you don’t know XX – your task is to find it. To achieve this, you can ask queries to obtain information about XX.

To be specific, you can ask queries in the form:

Find the Special Node solution codechef? Y 

where 1YN1≤Y≤N, and you will be provided with a random node on the path from node YY to node XX, excluding YY. If Y=XY=X you will receive 1−1 instead.

You can ask at most 1212 queries. Find the special node XX.

Note: The judge is not adaptive, i.e, node XX is chosen at the start before any interaction happens and does not change based on the queries you ask.

Interaction Find the Special Node solution codechef

  • Begin the interaction by reading a single integer TT denoting the number of test cases. The test cases follow.
  • For each test case, first read a single integer NN denoting the number of nodes in the tree.
  • N1N−1 lines follow. The ithith of these lines contains two space-separated integers uiui and vivi, denoting an edge between the nodes uiui and vivi.
  • After this, you can start making queries.
  • To ask a query, output ? Y (1YN1≤Y≤N). The judge will return some node (other than YY) which lies on the path between node YY and node XX, or 1−1 if Y=XY=X.
  • To output the answer, output ! X, where XX is the special node that is hidden. This is not considered a query.
  • If at any time you make an invalid query or exceed the query limit, the interaction is terminated and you will receive a Wrong Answer verdict.
  • Don’t forget to flush the output after printing each line!

Constraints

  • 1T101≤T≤10
  • 3N10003≤N≤1000
  • 1ui,viN1≤ui,vi≤N
  • It is guaranteed that the given nodes and edges construct a tree.
  • 1XN1≤X≤N

Sample Interaction

Grader                You
2
4
1 2
1 3
1 4
                      ? 1
-1
                      ! 1
4
1 2
2 3
3 4 
                      ? 1 
2          
                      ? 2
3
                      ? 3
-1
                      ! 3

Explanation Find the Special Node solution codechef

  • Test case 11: X=1X=1.

    • The query ? 1 gives 1−1.
    • A query returns 1−1 only if Y=XY=X, hence we can answer X=1X=1.
  • Test case 22: X=3X=3.

    • The query ? 1 gives node 22 which is in the path from node 11 to node 33 excluding node 11. That is the path between node 22 to node 33.
    • The query ? 2 gives node 33 which is in the path from node 22 to node 44 excluding node 22. That is the path between node 33 to node 33.
    • The query ? 3 gives 1−1 as Y=XY=X in this case, hence we can answer node 33.

NOTE: The above queries are just to demonstrate the interaction. They may or may not be sufficient to deduce the final answer.

Leave a Comment