Ivan Pesic and His World Tour
All submissions for this problem are available.### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME73/hindi/QRYLAND.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME73/bengali/QRYLAND.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME73/mandarin/QRYLAND.pdf), [Russian](http://www.codechef.com/download/translated/LTIME73/russian/QRYLAND.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME73/vietnamese/QRYLAND.pdf) as well. Chef is very popular, so his friends visit him often. Chef's friend Pesic decided to come visit him in Chefland during one of Pesic's famous world tours, but he got lost along the way and ended up in Queryland. Queryland has a weird structure: it has $N$ cities (numbered $1$ through $N$) and $N-1$ bidirectional roads connecting them in such a way that it is possible to reach any city in Queryland from any other city. Pesic visited all cities in Queryland and assigned values to them according to his experiences. Let's denote the initial value of city $i$ by $A_i$. Now that Pesic has seen all cities, he wants to play in Queryland for a bit longer. He has $Q$ queries of two types: - `1 X Y`: Consider the shortest path between cities $X$ and $Y$. Let's denote the length (number of cities, including the endpoints) of this path by $L$. Check whether the values of cities on this path (including the endpoints) form a permutation of the integers $1$ through $L$. - `2 X Z`: Change the value of city $X$ to $Z$. You are a big fan of Pesic, so he lets you process these queries for him. ### 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 space-separated integers $N$ and $Q$. - The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$. - Each of the next $N-1$ lines contains two space-separated integers $u$ and $v$ denoting that cities $u$ and $v$ are connected by a road. - The following $Q$ lines describe queries. - Each of these lines starts with an integer $t$ denoting the type of the current query: $t = 1$ for a query of the first type or $t = 2$ for a query of the second type. - If $t = 1$, it is followed by a space and two space-separated integers $X$ and $Y$ describing a query of the first type. - Otherwise, it is followed by a space and two space-separated integers $X$ and $Z$ describing a query of the second type. ### Output For each query of the first type, print a single line containing the string `"Yes"` if the values on the given path are a correct permutation or `"No"` if they are not. ### Constraints - $1 \le T \le 10$ - $1 \le N, Q \le 250,000$ - $1 \le u, v \le N$ - $1 \le X, Y, Z \le N$ - $1 \le A_i \le N$ for each valid $i$ - the sum of $N$ over all test cases does not exceed $500,000$ - the sum of $Q$ over all test cases does not exceed $500,000$ ### Subtasks **Subtask #1 (10 points):** $N, Q \le 1,000$ **Subtask #2 (40 points):** $v = u+1$ for each road **Subtask #3 (50 points):** original constraints ### Example Input ``` 1 10 5 1 2 3 4 5 6 7 8 9 10 1 2 1 3 2 4 2 5 3 9 4 10 5 6 5 7 5 8 1 4 3 1 10 3 2 10 5 1 10 3 1 5 3 ``` ### Example Output ``` Yes No Yes No ``` ### Explanation - Query 1: The values of cities on the path between cities $4$ and $3$ are $4$, $2$, $1$ and $3$, so they form a permutation of $1, 2, 3, 4$. - Query 2: The values of cities on the path between cities $10$ and $3$ are $10$, $4$, $2$, $1$ and $3$, so they do not form a permutation of $1, 2, 3, 4, 5$. - Query 3: The value of city $10$ changes from $10$ to $5$. - Query 4: The values of cities on the path between cities $10$ and $3$ are now $5$, $4$, $2$, $1$ and $3$, which is a permutation of $1, 2, 3, 4, 5$. - Query 5: The values of cities on the path between cities $5$ and $3$ are $5$, $2$, $1$ and $3$, which is not a permutation of $1, 2, 3, 4$.
|Tags||heavy-light-decomposition, ltime73, mo-algorithm, randomized, segment-tree, taran_1407, thesitzr|
|Time Limit:||4 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.