Tuco meets Heisenberg
All submissions for this problem are available.
Tuco, the gangster has got bags of meth from Heisenberg. Before giving him money, he asks Heisenberg to solve a problem. As Heisenberg is weak at coding, can you help him get his money.
You are given an undirected tree of N nodes rooted at 1. You need to find the sum of special function F(x) for each node x (1 ≤ x ≤ N). Let y be any node in the subtree of node x such that path from x to y is a smart path.Then F(x) is equal to the count of such nodes y. A smart path is defined as a path in which gcd of values of any two distinct nodes in the path is equal to 1.
Note: A path of single node is considered as a smart path.
The first line of the input contains an integer N denoting the number of nodes in the tree.
The next N-1 lines each containing an integer P, denoting the parent of nodes from 2 to N.
The next N lines each containing an integer V, denoting the value of ith node.
Output the required answer.
- 1 ≤ N,V ≤ 200000
- 1 ≤ P ≤ N
Input: 5 1 2 2 1 5 3 10 6 2 Output: 8
Example case 1.
The set of possible paths included in the answer are : [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ], [ 1, 2 ], [ 1, 5 ], [ 2,3 ]
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY|
Fetching successful submissions