Sum Of Node Values :
Difficulty Level : Hard
Submissions : 325
Asked In :
Marks :20
: 6 | : 0
You are given a tree of $$$N$$$ nodes rooted at node $$$1$$$.
Each node also has a value associated with it, given as an array $$$val$$$ of size $$$N$$$.
For each node $$$V$$$, you have to calculate the number of nodes in the subtree of $$$V$$$ whose value is co-prime with the value of $$$V$$$.
You need to return the sum of this value for all nodes in the tree as an answer.
The first line contains a single integer $$$1\le N \le 10^{5}$$$.
The second line contains $$$N$$$ space separated integers where $$$1\le i \le N$$$ integer denotes $$$1≤val[i]≤1000$$$ , value of node.
Following $$$N−1$$$ lines contains two space separated integers $$$u$$$ and $$$v$$$ which denotes $$$u$$$ and $$$v$$$ are connected by an edge.
Output the sum of the above mentioned value in the statement for all nodes in the tree.
5 1 2 3 4 5 1 2 1 3 3 4 3 5
6
10 2 7 3 2 4 8 8 1 1 12 1 2 1 3 2 4 1 5 3 6 5 7 5 8 8 9 8 10
10
In the first sample test case.
For node $$$1$$$, the nodes in its subtree whose values are co-prime with value of $$$1$$$, i.e. $$$val[1]=1$$$ are: $$$2,3,4$$$ and $$$5$$$. Count: $$$4$$$
For nodes $$$2,4$$$ and $$$5$$$ there are no such nodes.
For node $$$3$$$, the nodes in its subtree whose values are co-prime with value of $$$3$$$ i.e. $$$val[3]=3$$$ are: $$$4$$$ and $$$5$$$. Count: $$$2$$$.
So final answer = $$$4+0+2+0+0=6$$$.
