We heard you like trees. But this problem has no relation to trees being frozen. :D
You are given a rooted tree with $n$ nodes. The node with index $1$ is the root. Although the tree is not frozen, the tree is colorful. Each of the nodes is colored with a color identified by an integer from $1$ to $m$.
You will also be given an array of integers of $m$ length. Let's call this array $A$.
There are two types of operations. They are:
Operation 1:$1 ~i ~x$.
Set the value of $A[i]$ to $x$. It means perform the assignment $A[i] = x$.
Operation 2:$2 ~v ~l ~r$.
Consider the subtree rooted at node $v$. Lets count occurrences of all the $m$ colors in the subtree. We will denote this using $F_v$. It means the $i^{th}$ color appears $F_v [i]$ times in the subtree rooted at node $v$.
You have to tell if the following statement is true:
Is $F_v [i] = A[i]$ for all $i$ such that $l ≤ i ≤ r$ ?
In other words, does the following equation$F_v [l, l + 1, l + 2, ... r] = A[l, l + 1, l + 2, ... r]$
hold?
You have to print "YES" if the equation is true, otherwise print "NO" (without the quotes).
Input
First line will contain three integers $n, ~m, ~q$. They represent the number of nodes, the length of the array $A$ and the number of operations respectively.
The next line contains $n$ integers, $c_1, ~c_2, ~c_3 ... ~c_n; ~c_i$ is the color of the $i^{th}$ node.
The next line contains $m$ integers, $a_1, ~a_2, ~a_3 ... ~a_m$;
the $A$ array.
Next $n-1$ lines contain the $u ~v$ pairs. They represent the edges in the tree.
Next $q$ line will describe the operation.
For type - 1 operation the input is:$1 ~i ~x$.
For type - 2 operation input format is:$2 ~v ~l ~r$.
Constraints:$1 ≤ m ≤ 5 × 10^4$.$1 ≤ n ≤ 5 × 10^4$.$1 ≤ q ≤ 5 × 10^4$.$1 ≤ c_i ≤ m$.$1 ≤ a_i ≤ 10^9$.$1 ≤ u, ~v ≤ n$.
For type 1 operation:$1 ≤ i ≤ m$.$0 ≤ x ≤ 10^9$.
For type 2 operation:$1 ≤ v ≤ n$.$1 ≤ l ≤ r ≤ m$.
Output
For each of the type-2 operations, print "YES" or "NO" without the quotes.
Sample
| Input | Output |
|---|---|
7 4 4 1 1 2 4 4 3 3 2 1 2 3 1 2 2 4 2 5 3 6 3 7 1 3 2 3 2 3 2 3 1 3 1 1 0 2 3 1 3 | YES NO YES |
