All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

Rescue Brook
/
No tags
Problem
Editorial
Analytics

natsu and igneel

Brook has been captured by Big Mom one of the emperor of the sea. His friends are trying to rescue him while Big Mom is sleeping. The path to his rescue is in the form of a tree having N nodes and each node has a weight. The tree is rooted at 1. The nodes with prime weight might have traps. Hence his friends while travelling wants to know how many nodes have prime weights in the subtree of a certain node(including that node itself). The values of weights can change while they travel. Their is a device near the wall which also tells which node is updated to what value. Help them to rescue Brook if you can.


PS : Enormous I/O

Constraints:
1 ≤ T ≤ 4
1 ≤ N, Q ≤ 3,00,000
-3,00,000 ≤ Weight ≤ 3,00,000

Input:
First line contains the number of test cases T.
For each of the T test cases first line contains two space separated integers N number of nodes in the tree and Q number of queries receptively.
Next line contain N space separated integers denoting the values of the node 1,2,..N respectively.
Next N-1 line contains two integers u and v denoting there exists an edge between node u and v.
Next Q lines contain two types of query:
Type 1 : 1 u x - Replace value of node u by x.
Type 2 : 2 u - Print number of primes in the sub tree of node u.

Output:
For each query of type 2 print the answer in a new line.

SAMPLE INPUT
2
3 3
2 7 9
1 2
1 3
2 1
1 3 5
2 1
5 5
1 4 1 2 7 
4 2
5 3
1 3
5 4
1 1 2
2 2
1 3 5
2 3
2 1
SAMPLE OUTPUT
2
3
0
3
4
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?