3.
Utkarsh and Ancestor Queries
Max. Marks 100

Utkarsh was playing with a rooted tree of N nodes. Each node is numbered from 1 to N. Assume 1 as the root. Each node i has two integers Ai an Bi associated with it.

You need to answer Q queries of 2 types
1 v x : update Av = x
2 v : Tell how many nodes p are there such that p is an ancestor of v and Ap ≤ Bv

Note: P is an ancestor of v if P = v or P is ancestor of parent of v.

Input:
First line contains two integers N and Q.
Following N-1 lines contains pair of integers a b denoting there is an edge between a and b.
Next line contains N integers denoting the Array A
Next line contains N integers denoting the Array B
Next Q lines describe Q queries.

Output:
For each query of type 2 output the required answer.

Constraints:
1 ≤ N ≤ 6104
1 ≤ Q ≤ 8
104
1 ≤ Ai, Bi, x ≤ 105


Sample Input

(Plaintext Link)

10 10
2 1
3 1
4 3
5 1
6 3
7 6
8 6
9 2
10 8
4 2 2 2 4 2 1 4 2 1
3 5 3 2 5 3 3 2 3 2
2 3
1 9 5
1 6 4
1 3 2
2 6
1 8 5
1 6 2
1 7 3
2 9
2 1
Sample Output

(Plaintext Link)

1
1
1
0

 

 

no answer

Advertisements