G. Super Glue

Codeforces

IDCF10256G

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Mickey is a very cheeky boy who recently found two interesting items. The first item is a special type of glue - called SuperGlue and the other one is a very rare rooted tree. The tree itself is #cf_span(class=[tex-font-style-underline], body=[binary]), which means that all of its nodes are leafs or either having two sons, where a leaf is a node without any sons. Moreover, the tree is that interesting such that it is #cf_span(class=[tex-font-style-underline], body=[fully balanced]). A tree is #cf_span(class=[tex-font-style-underline], body=[fully balanced]) when: where $l_i$ and $l_j$ are any two leafs in the tree. By $d i s t (i, j)$ we mean the distance from node $i$ to node $j$. Mickey was wondering a lot how to combine those two items, and in the end, he decided to take a subtree from the tree (which was not the tree itself) and to glue this one to a leaf which is not part of it. Time flew and Mickey forgot what he has done but now he wants to revert the tree to its original state! The first line of the input will contain the number of nodes $N <= 15 * 10^5$ of the resulting tree. The following $N -1$ lines will each contain an edge between two nodes of the resulting tree. You should output three numbers on the same line: The tree from the input is: The original tree is as follows: ## Input The first line of the input will contain the number of nodes $N <= 15 * 10^5$ of the resulting tree. The following $N -1$ lines will each contain an edge between two nodes of the resulting tree. ## Output You should output three numbers on the same line: the node representing the root of the original tree. the node representing the root of the subtree that was glued; this subtree is defined based on the original root found in the above bullet. the node to which the subtree has to be glued to retrieve the original tree. If there exist multiple solutions, output any of them. [samples] ## Note The tree from the input is: The original tree is as follows:

**Definitions** Let $ n \in \mathbb{Z} $ with $ 2 \leq n \leq 1000 $. Let $ N = \{1, 2, \dots, n\} $ be the set of nut sizes. Let $ B = \{1, 2, \dots, n\} $ be the set of bolt sizes. There exists a unique bijection $ \sigma: N \to B $ such that nut $ i $ matches bolt $ \sigma(i) $. **Constraints** 1. At most $ 5n \log_2 n $ comparison queries may be made. 2. Each query: output `? i j` to compare nut $ i $ and bolt $ j $, receive one of: - `<` if $ i < j $, - `>` if $ i > j $, - `=` if $ i = j $. **Objective** Determine the permutation $ p = (p_1, p_2, \dots, p_n) $ such that $ p_i = \sigma(i) $, i.e., nut $ i $ matches bolt $ p_i $. Output `! p_1 p_2 ... p_n` and terminate.

API Response (JSON)

{
  "problem": {
    "name": "G. Super Glue",
    "description": {
      "content": "Mickey is a very cheeky boy who recently found two interesting items. The first item is a special type of glue - called SuperGlue and the other one is a very rare rooted tree. The tree itself is #cf_s",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10256G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mickey is a very cheeky boy who recently found two interesting items. The first item is a special type of glue - called SuperGlue and the other one is a very rare rooted tree. The tree itself is #cf_s...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 1000 $.  \nLet $ N = \\{1, 2, \\dots, n\\} $ be the set of nut sizes.  \nLet $ B = \\{1, 2, \\dots, n\\} $ be the set of bolt sizes.  \nThere exi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments