Guess the Binary Tree

View as PDF
Submit solution
Points: 0.01 (partial)
Time limit: 4.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

This is an interactive problem

You are given a rooted binary tree with ~2\cdot n - 1~ vertices numbered from ~1~ to ~2\cdot n - 1~. The tree's root is the node ~2\cdot n - 1~. In the tree, vertices ~1, 2, \ldots, n~ are leaves. The remaining vertices ~p~ (~n < p < 2\cdot n~) satisfy the following properties:

  • vertex ~p~ has exactly two children, a left child ~a_p~ and a right child ~b_p~;

  • for any pair of leaves ~u~, ~v~ (~1 \le u, v \le n~) such that ~a_p~ is an ancestor∗ of ~u~ and ~b_p~ is an ancestor of ~v~, we have ~u < v~

For ~1 \le l \le r \le n~, define ~f(l, r)~ as the number of elements of the set of vertices ~S~ satisfying the following conditions:

  • for ~l \le u \le r~, there exists an ancestor of ~u~ in ~S~;

  • for ~1 \le u < l~ or ~r < u \le n~, there does not exist any ancestor of ~u~ in ~S~;

  • among all vertex sets that satisfy the above two conditions, ~S~ has the smallest number of vertices.

You are given the integer ~n~, but the tree structure is unknown in advance. You need to interact with the organizer's program to determine the structure of the binary tree. You may ask queries of the form ~l, r~ (~1 \le l \le r \le n~), and the response you receive is ~f(l, r)~.

Once the tree structure has been determined, you must provide the list of children ~a_p~ and ~b_p~ for each vertex ~n < p < 2 \cdot n~. Your answer is considered correct if the following conditions are satisfied:

  • you ask no more than ~n^2~ queries;

  • the tree structure satisfies the properties stated above;

  • for every pair of integers ~l, r~ (~1 \le l \le r \le n~), the value ~f(l, r)~ computed from your tree must equal ~f(l, r)~ computed from the jury's tree.

If there are multiple answers satisfying the above conditions, output any valid one.

In this problem, the score you receive depends on the number of queries you ask. See the scoring section for details.

∗ Vertex ~p~ is called an ancestor of ~u~ if ~p = u~, or ~p~ is not a leaf and one of the children of ~p~ is an ancestor of ~u~.

Interaction

First, you need to read an integer ~t~ (~1 \le t \le 150~) – the number of test cases. For each test case, the interaction proceeds as follows:

  • First, read an integer ~n~ (~2 \le n \le 150~) – the number of leaves of the tree.

  • To make a query, print ? ~l \ r~ (~1 \le l \le r \le n~), then read an integer ~f(l, r)~.

  • When you have determined the structure of the tree, print a line containing the character !, then print ~2n - 2~ integers ~a_{n+1}, b_{n+1}, a_{n+2}, b_{n+2}, \ldots, a_{2n-1}, b_{2n-1}~ – the list of children of the vertices ~n + 1, n + 2, \ldots 2 \cdot n - 1~.

    If there are multiple correct answers, output any valid one.

The tree is fixed before the interaction begins, and it will not change during the interaction.

It is guaranteed that the sum of ~n~ over all test cases does not exceed ~150~.

After printing a command, do not forget to print a newline and flush the standard output. To do this, you may use:

  • fflush(stdout) or cout.flush() in C++;

  • System.out.flush() in Java;

  • flush(output) in Pascal;

  • stdout.flush() in Python;

  • see the standard documentation for other languages.

Scoring

Let ~q~ be the number of queries you ask. Your score for a test case is:

Condition Score
~2\cdot n \lt q \le n^2~ ~1000~
~q \le 2n~ ~2000~

The score of an input set is the minimum score among its test cases. Your score for this problem is the minimum score among all input sets.

Sample Input 1

2
3

2

1

4

2

2

1

Sample Output 1

? 1 2

? 2 3

! 2 3 1 4

? 1 3

? 2 4

? 1 4

! 1 2 3 4 5 6

Notes

In the first example, the queries are as follows:

  • ~f(1, 2) = 2~. Here ~S = \{ 1, 2 \}~

  • ~f(2, 3) = 1~. Here ~S = \{ 4 \}~

image

Illustration of the first example

In the second example, one can choose a set ~S~ of minimum size corresponding to the given ~f~ values as follows:

  • ~f(1, 3) = 2~. Here ~S = \{ 3, 6 \}~

  • ~f(2, 4) = 2~. Here ~S = \{ 2, 5 \}~

  • ~f(1, 4) = 1~. Here ~S = \{ 7 \}~

image

Illustration of the second example

Comments

Please read the guidelines before commenting.


  • 8
    ProTeam15  commented on May 17, 2026, 4:50 a.m.

    Bản chất thì ~f(l, r)~ là số nút ít nhất cần để phủ hết đoạn từ ~l \rightarrow r~.

    Để dễ tưởng tượng bài này hơn bạn có thể nghĩ đang làm việc với Segment Tree. Ý tưởng sơ khai là mỗi lẫn bạn truy vấn trên ST thì số lượng nút bạn đụng đến không quá ~log(n)~. Tại sao điều đó lại diễn ra??? Lí do là có sự gộp nút ở đây, nếu như đoạn truy vấn có cả nút ~2\times id ~ và ~2\times id + 1~ thì có thể gộp nó lại thành nút ~id~.

    Qua cái nhìn trên mình có thể đưa ra ý tưởng là nếu hiện tại đang biết đoạn từ ~1 \rightarrow i-1~ sau đó mình thêm nút ~i~ vào thì sẽ xảy ra bao nhiêu lần gộp. Và mỗi lần gộp như thế nó sẽ tác động đến ~2~ đỉnh nào?? Và sau khi gộp ~2~ đỉnh đó lại thì nó biến thành đỉnh nào?? Giả sử gộp ~2~ đỉnh ~A, B~ thành một đỉnh mới là ~C~ thì ta có ~L[C] = A~, ~R[C] = B~.

    Để biết nó tác động đến ~2~ đỉnh nào thì ta cần duy trì các đỉnh hiện tại cần để phủ và đặt ra các câu hỏi ~f(1, i)~ để biết rằng có bao nhiêu lần gộp, từ số lần gộp sẽ thấy cái tập đỉnh duy trì để phủ hết sẽ biến đổi như thế nào.

    Giả sử gọi tập đỉnh duy trì để phủ hết là ST:

    • Ta đang phủ hết đoạn ~1 \rightarrow i - 1~, bây giờ thêm đỉnh ~i~ vào. Suy ra ST sẽ thêm ~i~.
    • Sau đó nó sẽ bắt đầu quá trình gộp, thì gộp sẽ tác động lên ~2~ đỉnh cuối trong ST.
    • Số lần gộp là: ~f(1, i - 1) + 1 - f(1, i)~.
    • Sau khi gộp ~2~ đỉnh cuối lại thì nó tạo ra đỉnh nào?? => Đỉnh tiếp theo chưa xuất hiện.

    Vậy chỉ cần tốn tổng cộng ~n - 1~ truy vấn là có thể xây dựng lại cây ban đầu.

    Code tham khảo:

    #include<bits/stdc++.h>
#define int long long
#define oo 1000000000000000000
#define ii pair<int, int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define pb push_back
using namespace std;

const int mod = 998244353;

void add(int &x, int y) {
   x += y;
   if(x >= mod) x -= mod;
}
void sub(int &x, int y) {
   x -= y;
   if(x < 0) x += mod;
}

int n;
int need[1005]; // f[1 -> i]
int a[1005], b[1005];

int ask(int l, int r) {
   cout << "? " << l << " " << r << endl;

   int cnt; cin >> cnt;
   return cnt;
} 

void solve() {

   /*
   Về mặt bản chất f(l, r) là số đỉnh ít nhất để phủ đoạn đỉnh [L -> R]

   nếu mình tính đc số lần các nút gộp vào nhau để tạo thành nút lớn hơn => mình sẽ biết đc đó là 2 nút con của thằng cha.

   1 -> (i - 1) thêm i thì gộp bao nhiêu lần?
   hỏi f(1, i) trừ đi f(1, i - 1) + 1 -- +1 là do thêm đỉnh mới là i vào

   giờ có số lần gộp rồi thì làm gì??
   mấy lần gộp đó tác động lên thằng nào???
   2 thằng cuối, nma 2 thằng cuối gộp lại thì thành gì???? => thành thằng tiếp theo chưa có
   */

   cin >> n;

   need[1] = 1;
   for(int i = 2; i <= n; i++) {
       need[i] = ask(1, i);
   }

   stack<int> st;
   st.push(1);
   int cur = n;
   for(int i = 2; i <= n; i++) {
       st.push(i);
       int gop = need[i - 1] + 1 - need[i];
       for(int j = 1; j <= gop; j++) {
           int y = st.top(); st.pop();
           int x = st.top(); st.pop();
           cur++;
           a[cur] = x;
           b[cur] = y;
           st.push(cur);
       }
   }

   cout << "! ";
   for(int i = n + 1; i < 2 * n; i++) {
       cout << a[i] << " " << b[i] << " ";
   }
   cout << endl;
}

signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   // if(fopen("a.inp", "r")) {
   //     freopen("a.inp", "r", stdin);
   //     freopen("a.out", "w", stdout);
   // }

   int t = 1;
   cin >> t;
   while(t--) {
       solve();
   }
}