Forgotten Tree 9

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/JUNE19/hindi/FGTREE.pdf), [Bengali](http://www.codechef.com/download/translated/JUNE19/bengali/FGTREE.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/JUNE19/mandarin/FGTREE.pdf), [Russian](http://www.codechef.com/download/translated/JUNE19/russian/FGTREE.pdf), and [Vietnamese](http://www.codechef.com/download/translated/JUNE19/vietnamese/FGTREE.pdf) as well. There is a rooted binary tree with $N$ nodes. For each node with exactly two children, one of them is called the left child and the other is called the right child. If a node has only one child, it is still specifically called either the left child or the right child. The nodes are labelled $1$ through $N$ according to the inorder traversal of the tree. That is, the labelling can be generated by the following pseudocode: ``` integer index = 1 function dfs(node n): if n has left_child: dfs(n.left_child) n.label = index index += 1 if n has right_child: dfs(n.right_child) run dfs(root) ``` For each node $x$, the subtree of this node consists of the node $x$ itself and all its (direct or indirect) descendants. Since the nodes are labelled according to inorder traversal, the subtree of node $x$ can be described by two integers $a_x$ and $b_x$ in the following way: the nodes $a_x, a_x+1, \ldots, b_x$ all belong to the subtree of node $x$ and all other nodes do not belong to this subtree. You do not know the structure of the tree. You would like to reconstruct it by asking questions in the form: "Is $a_x$ equal to $a$ and also $b_x$ equal to $b$?" You may ask at most $300$ such questions. Find the root and the parent of each nonroot node. ### Interaction  First, you should read a line containing a single integer $T$ — the number of test cases. The description of interaction for $T$ test cases follows.  For each test case, you should start by reading a line containing a single integer $N$.  Afterwards, you may ask questions. To ask a question, print a line containing the character 'Q' followed by a space and three spaceseparated integers $x$, $a$ and $b$ ($1 \le x \le N$, $1 \le a \le x \le b \le N$). Then, you should read a line containing the string `"Yes"` if $a$ is equal to $a_x$ and $b$ is equal to $b_x$ or `"No"` otherwise.  When you are ready to answer, print a line containing the character 'A' followed by a space and $N$ spaceseparated integers $p_1, p_2, \ldots, p_N$. For each valid $i$, $p_i$ should denote the parent of the $i$th node or, if the $i$th node is the root, it should be $1$. Your answer will be considered correct if it exactly describes the hidden tree. Don't forget to flush the output after printing each line! ### Constraints  $1 \le T \le 100$ ### Subtasks **Subtask #1 (20 points):** $1 \le N \le 10$ **Subtask #2 (20 points):** $1 \le N \le 20$ **Subtask #3 (30 points):** $1 \le N \le 50$ **Subtask #4 (30 points):** $1 \le N \le 100$ ### Example Input ``` Grader  You 2  2   Q 1 1 2 No   A 2 1 5   Q 4 1 5 Yes   Q 1 1 4 No   Q 3 1 3 Yes   Q 1 1 2 Yes   A 3 1 4 1 4 ``` ### Explanation **Example case 1:** The tree has only two nodes — node $2$ is the root and node $1$ is its left child. In this case, we have $a_1 = 1$, $b_1 = 1$, $a_2 = 1$ and $b_2 = 2$. First, we ask if the subtree of node $1$ subtree contains the nodes $1$ and $2$. The answer is "No", so we know that node $2$ is the root and node $1$ is its child, which is what we needed to find out. **Example case 2:** In the first question, we ask if nodes $1$ through $5$ are all in the subtree of node $4$. In this case, the answer is "Yes", so we know that node $4$ is the root of the whole tree. We still need to ask more questions to determine how nodes $1$, $2$, $3$ and $5$ are connected to it.Author:  lg5293 
Editorial  https://discuss.codechef.com/problems/FGTREE 
Tags  june19, junechallenge, lg5293 
Date Added:  9052019 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions