Nearest Color

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK106/hindi/COLORDIS.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK106/mandarin/COLORDIS.pdf), [Russian](http://www.codechef.com/download/translated/COOK106/russian/COLORDIS.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK106/vietnamese/COLORDIS.pdf) and [Bengali](http://www.codechef.com/download/translated/COOK106/bengali/COLORDIS.pdf) as well. You have to process $Q$ queries on a rooted tree. Each node of the tree has a label and a color. Initially, the tree consists of a single node (the root) with label $1$ and color $c_0$. There are two types of queries: 1. You are given an existing node $u$ and a color $c$. Let's denote the number of nodes in the tree before this query by $k$. Create a node with label $k+1$ and color $c$, and add it to the tree as a child of node $u$. 2. You are given a node $u$ and a color $c$. For each node with color $c$ (possibly including $u$), find its distance from node $u$. The answer to this query is the minimum of these distances, or $1$ if there are no nodes with color $c$ in the tree. The input is encoded so that you have to process these queries online. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $Q$ and $c_0$.  Each of the following $Q$ lines contains a character $t$ followed by a space and two spaceseparated integers $u'$ and $c'$ describing a query.  The character $t$ is '+' for a query of the first type or '?' for a query of the second type.  Let's denote the answer to the last query of the second type by $a$ ($a = 1$ if there have been no queries of the second type so far). The parameters $u$ and $c$ of the current query can be computed as $u = u' \oplus (a+1)$ and $c = c' \oplus (a+1)$. ### Output For each query of the second type, print a single line containing one integer — the answer to this query. ### Constraints  $1 \le Q \le 2 \cdot 10^5$  the sum of $Q$ over all test cases does not exceed $4 \cdot 10^5$  $t$ is '+' or '?'  $u$ is a valid label of a node in the tree  $1 \le c_0, c \le 2 \cdot 10^5$ ### Example Input ``` 2 6 1 + 1 2 + 2 3 + 3 1 ? 1 3 ? 7 2 ? 3 0 10 1 + 1 2 ? 1 1 ? 3 0 ? 0 6 + 2 3 + 2 4 ? 3 4 + 0 7 ? 0 7 ? 3 6 ``` ### Example Output ``` 2 0 1 0 1 1 2 1 2 ``` ### Explanation **Example case 1:** The decoded queries are ``` + 1 2 + 2 3 + 3 1 ? 1 3 ? 4 1 ? 2 1 ``` **Example case 2:** The decoded queries are ``` + 1 2 ? 1 1 ? 2 1 ? 2 4 + 2 3 + 2 4 ? 3 4 + 3 4 ? 3 4 ? 1 4 ```Author:  anachor 
Editorial  https://discuss.codechef.com/problems/COLORDIS 
Tags  anachor, cookoff, cook106 
Date Added:  15052019 
Time Limit:  8 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
HELP
If you are still having problems, see a sample solution here. 