Tree Traversal CodeChef Solution


Tree Traversal Happiness CodeChef Solution

Tree Traversal CodeChef Solution

There is a hidden tree with NN vertices labeled 1,2,…,N1,2,…,N.

Your task is to recover the edges of the tree. You can ask queries, where you give a set SS of size at least 22 to the judge.

  • Call a vertex¬†x‚ąąSx‚ąąS¬†isolable, if there exists an edge in the tree such that if we remove this edge, no other vertex¬†y‚ąąSy‚ąąS¬†is reachable from¬†xx.

  • The judge returns two integers, the first one being some isolable vertex of set¬†SS, and the second one being the sum of the labels of all the isolable vertices of set¬†SS.

There are multiple testcases. The sum of the number of queries asked over all the testcases should not exceed 104104.

The judge is not adaptive, which means that the tree is fixed before you ask any queries. Also, the judge is not guaranteed to be deterministic, that is, when queried twice for the same set SS, the isolable vertex returned might be different, but the sum of all isolable vertices will be the same.

Input Format

  • First, you should read a single integer¬†TT, the number of test cases.
  • For each test case, first read the value of¬†NN.
  • To query for a set¬†S={s1,s2,‚Ķ,sk}S={s1,s2,‚Ķ,sk}, print¬†?¬†followed by¬†kk, followed by¬†kk¬†space-separated integers¬†s1,s2,‚Ķ,sks1,s2,‚Ķ,sk.
  • If the query format is incorrect or the total number of queries asked over all the testcases till now exceeds¬†104104, the judge prints¬†-1, and exits with a wrong answer verdict. In this case, you must also terminate your program.
  • Otherwise, the judge prints two integers, as described in the problem statement.
  • Once you know all the edges of the tree, print¬†!¬†on one line. On each of the next¬†N‚ąí1N‚ąí1¬†lines, print the endpoints of an edge of the tree. The edges can be printed in any order.
  • If the edges printed by you match those of the hidden tree, the judge prints¬†1, and you should move to the next testcase (if any), else the judge prints¬†-1, and exists with a wrong answer verdict. In the latter case, you must terminate your program as well.

Interaction Example

You                     Grader
                        3           # 3 test cases
                        6           # N = 6
? 3 1 6 3
                        6 9         # The isolable vertices in
                                    # S = {1, 3, 6} are 3 and 6

? 2 2 5
                        2 7         # Both 2 and 5 are isolable

1 2
2 5
3 2
4 1
4 6

                        1           # Correct answer! 

                        3           # Next test case, N = 3

? 3 1 2 3
                        1 3         # 1 and 2 are isolable
1 2
2 3
                        -1          # Incorrect output! Judge exits

You should also
terminate here
without reading
the next test case

Tree Traversal CodeChef Solution


The first testcase is the following:

The second testcase has 33 vertices, with edges (1,3)(1,3) and (2,3)(2,3).


  • 2‚ȧN‚ȧ10002‚ȧN‚ȧ1000
  • The sum of¬†NN¬†over all testcases doesn’t exceed¬†10001000


Tree Traversal CodeChef Solution

  • Subtask 1 (13 points):¬†The tree is a path.
  • Subtask 2 (20 points):¬†The sum of¬†NN¬†over all testcases doesn’t exceed¬†100100.
  • Subtask 3 (23 points):
    • The number of leaves in the tree doesn’t exceed¬†1010.
    • The sum of¬†NN¬†over all testcases doesn’t exceed¬†500500.
  • Subtask 4 (44 points):¬†No additional constraints.

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.

If You Want To Learn Something New Then Visit Our Official Channel YOUTUBE

Related Posts

Leave a Reply

Your email address will not be published.