Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Freezing Trees

By souravvv · Limits 1s, 512 MB

We heard you like trees. But this problem has no relation to trees being frozen. :D

You are given a rooted tree with nn nodes. The node with index 11 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 11 to mm.

You will also be given an array of integers of mm length. Let's call this array AA.

There are two types of operations. They are:

Operation 1:
1 i x1 ~i ~x.
Set the value of A[i]A[i] to xx. It means perform the assignment A[i]=xA[i] = x.

Operation 2:
2 v l r2 ~v ~l ~r.
Consider the subtree rooted at node vv. Lets count occurrences of all the mm colors in the subtree. We will denote this using FvF_v. It means the ithi^{th} color appears Fv[i]F_v [i] times in the subtree rooted at node vv.
You have to tell if the following statement is true:
Is Fv[i]=A[i]F_v [i] = A[i] for all ii such that lirl ≤ i ≤ r ?
In other words, does the following equation
Fv[l,l+1,l+2,...r]=A[l,l+1,l+2,...r]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, qn, ~m, ~q. They represent the number of nodes, the length of the array AA and the number of operations respectively.

The next line contains nn integers, c1, c2, c3... cn; cic_1, ~c_2, ~c_3 ... ~c_n; ~c_i is the color of the ithi^{th} node.

The next line contains mm integers, a1, a2, a3... ama_1, ~a_2, ~a_3 ... ~a_m;
the AA array.

Next n1n-1 lines contain the u vu ~v pairs. They represent the edges in the tree.

Next qq line will describe the operation.

For type - 1 operation the input is:
1 i x1 ~i ~x.
For type - 2 operation input format is:
2 v l r2 ~v ~l ~r.

Constraints:
1m5×1041 ≤ m ≤ 5 × 10^4.
1n5×1041 ≤ n ≤ 5 × 10^4.
1q5×1041 ≤ q ≤ 5 × 10^4.
1cim1 ≤ c_i ≤ m.
1ai1091 ≤ a_i ≤ 10^9.
1u, vn1 ≤ u, ~v ≤ n.

For type 1 operation:
1im1 ≤ i ≤ m.
0x1090 ≤ x ≤ 10^9.

For type 2 operation:
1vn1 ≤ v ≤ n.
1lrm1 ≤ l ≤ r ≤ m.

Output

For each of the type-2 operations, print "YES" or "NO" without the quotes.

Sample

InputOutput
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

Discussion

Statistics


81% Solution Ratio

tmwilliamlin168Earliest, Dec '19

mahdi.hasnatFastest, 0.1s

ShahinLightest, 10 MB

tmwilliamlin168Shortest, 1767B

Submit

Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.