Question

You are given a tree which consists of N nodes and an array A where A[U]

represents the value of node U.

You are also given an array P where P[U] denotes the parent of node U.

We define the beauty of the path from U to V as follows:

Write down the values written on the nodes of the simple path from U to V in

the order they appear.

Find the length of the longest subsequence such that for each pair of adjacent

elements, their ged is greater than 1.

Find the maximum possible beauty over all pairs of nodes.

Note:

It is given that P[1] is equal to 0.

Input Format

The first line contains an integer, N. denoting the number of elements in A

Each line i of the N subsequent lines (where 0 <= i < N ) contains an integer

describing A[i]

Each line i of the N subsequent lines (where 0 <= t < N ) contains an integer

describing P[i]

Constraints

1 <= N <= 10 ^ 5

1 <= A[i] <= 10 ^ 5

1 <= P[i] <= 10 ^ 5

Sample Test Cases

Case 1

Input:

1

999

0

Output:

1

Q

Explanation:

Given N 1, A [999], P= [0].

There exist only 1 node present in the Tree.

Hence, the answer for this case is equal to 1.

Case 2

Input:

2

43636

46964

0

1

Output:

2

Explanation:

Given N = 2, A [43636, 46964], P = [0, 1].

Since the values of both nodes are even then the gcd of the path is greater than 1.

Hence the answer for this case is equal to 2.

Case 3

Input

4

55305

63807

73880

50840

0

1

1

1

Q

Output:

3

Explanation:

Given N = 4, A [55305, 63807, 73880, 50840], P= [0, 1, 1, 1].

The optimal path consists of nodes [3, 1, 4] which has a gcd greater than 1.

Hence, the answer for this case is equal to 3.

def get_ans(N,A,P)

Answer 1

import math
from collections import defaultdict, deque
def get_ans(N, A, P):
 tree = defaultdict(list)
 for child in range(2, N+1):
 parent = P[child - 1]
 tree[parent].append(child)
 tree[child].append(parent)
 
 def gcd(a, b):
 return math.gcd(a, b)
 
 def bfs(start):
 queue = deque([(start, [A[start-1]])])
max_beauty = 1
 visited = set()
 visited.add(start)
 
 while queue:
 current, path = queue.popleft()
 for neighbor in tree[current]:
 if neighbor not in visited:
 visited.add(neighbor)
 new_path = path + [A[neighbor-1]]
 queue.append((neighbor, new_path))
 
 dp = [1] * len(new_path)
 for i in range(1, len(new_path)):
 for j in range(i):
 if gcd(new_path[i], new_path[j])
> 1:
 dp[i] = max(dp[i], dp[j] + 1)
 max_beauty = max(max_beauty, max(dp))
 
 return max_beauty
 
 overall_max_beauty = 1
 for node in range(1, N+1):
 overall_max_beauty = max(overall_max_beauty, bfs(nod
e))
 
 return overall_max_beauty
#if u faced gcd eroor
def gcd(x, y):
 while y:
 x, y = y, x % y
 return x