AlgoUniversity
  • Go Back
Discussion
Sum Of Node Values :

Author

Shikhar Mehrotra

Difficulty Level : Hard

Submissions : 343

Asked In : Uber

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.

Input

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

Output the sum of the above mentioned value in the statement for all nodes in the tree.

Examples

Input
5
1 2 3 4 5
1 2
1 3
3 4
3 5
Output
6
Input
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
Output
10

Note

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$$$.

You need to login to view your submissions.

You need to login to view all submissions.

Loading...

Result : Executed

Loading...

Feel something is wrong with the test cases?

Result : Accepted

Test Cases :

You need to Log In
We're glad that you want to attempt this problem!

But to Run or Submit the Problem, you need to Log In.

Continue to Log In
Challenge Submitted!

Your challenge has been submitted successfully.

You will get a response soon via WhatsApp or Email.

Challenge
Facing issue while trying to solve the problem! Don't worry, we got you covered!

Do let us know your issue.

Looks good!
Please enter your issue / feedback.

How do we get in touch with you?
Looks good!
Please enter your phone no.
Looks good!
Please enter your email address.