CF2277E Tree Guessing

[Maozon - Stasis](https://www.youtube.com/watch?v=seY45BJkUQE) This is an interactive problem. The interactor has a hidden tree with $ n $ vertices, numbered from $ 1 $ to $ n $ . Your task is to find this tree using at most $ 2n - 2 $ queries. In each query, you choose a vertex $ x $ and a permutation $ p_1, p_2, \ldots, p_n $ of the integers from $ 1 $ to $ n $ , and the interactor returns $$$ \sum_{i = 1}^{n} \max_{j \in \text{path}(i, x)} p_j, $$$ where $ \text{path}(i, x) $ is the set of vertices on the simple path between $ i $ and $ x $ , including both $ i $ and $ x $ (in particular, $ \text{path}(x, x) = \{x\} $ ). In other words, for each vertex $ i $ , consider all vertices $ j $ on the unique path from $ i $ to $ x $ , including both endpoints, and take the largest $ p_j $ among them. The interactor returns the sum of these maximum values over all $ n $ vertices $ i $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 250 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 500 $ ) — the number of vertices in the tree. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 500 $ .

N/A

In the first test case, the only possible tree on two vertices consists of the single edge $ (1, 2) $ , so no queries are needed. The answer is ! followed by this edge. In the second test case, the tree has two edges, $ (1, 2) $ and $ (1, 3) $ . In the first query, $ x = 1 $ and $ p = [1, 2, 3] $ , so the interactor returns $ \max\{1\} + \max\{2, 1\} + \max\{3, 1\} = 6 $ . In the second query, $ x = 2 $ and $ p = [1, 2, 3] $ , so the interactor returns $ \max\{1, 2\} + \max\{2\} + \max\{3, 1, 2\} = 7 $ .