Primes In Subtree :
Difficulty Level : Easy
Submissions : 276
Asked In :
Marks :50
: 2 | : 2
You are given a tree consisting of $$$n$$$ nodes and $$$m$$$ edges. The nodes are numbered from 1 to $$$n$$$. Each node has a positive integer value associated with it. You are given $$$q$$$ queries each of which consist of a node of the graph from 1 to $$$n$$$. Let this node be $$$x$$$. You need to find the number of prime values in the subtree rooted at node $$$x$$$ for each query.
The first line of input consists of two space separated integers $$$-$$$ $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^5)$$$ $$$(0 \leq m \leq n-1)$$$. The second line of input consists of $$$n$$$ space separated integers $$$-$$$ the values associated with the nodes of the graph, where the $$$i_{th}$$$ integer represents the value associated with the $$$i_{th}$$$ node of the graph. The next $$$m$$$ lines consist of 2 space separated integers $$$-$$$ which denote that there is an edge between the 2 nodes. The next line of input consists of a single integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$ $$$-$$$ the number of queries. The next line of input consists of $$$q$$$ space separated integers, where the $$$i_{th}$$$ number is the $$$i_{th}$$$ query.
The output should consist of $$$q$$$ space separated integers, where the $$$i_{th}$$$ integer is the answer to the $$$i_{th}$$$ query.
5 4 2 3 5 7 11 1 2 1 3 1 4 4 5 5 1 2 3 4 5
5 1 1 2 1
