Hello everyone, I have a rough solution in the end, but I need your views on this. Thanks in advance :)

You are given a tree of N nodes. The tree is rooted at node 1. Each tree node has a value associated with it and is represented as value. For each node, you are required to determine the closest ancestor that contains values that are co-prime to the current node value. If no such nodes exist, then print -1. Two integers a and b are relatively prime, mutually prime, or co-prime if the only positive integer (factor) that can divide both the integers is 1.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a node v is the last difference from v vertex the path from the root to vertex v. Children of vertex v are all nodes for which v is the parent. A vertex is a leaf if it has no children.

Input format

• The first line contains an integer T denoting the number of test cases.

• The first line of each test contains an integer N denoting the number of nodes in the tree.

• The next line of each test case contains N space-separated integers where the ih integer denotes the value at node i represented as value;

• Next N — 1 lines of each test case contain two space separated integers u and v denoting the edge

between node u and node u.

Output format

For each test case, print N space-separated integers where the i' integer denotes the closet ancestor contains coprime values. If no such ancestors exist then print -1.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
1 <= u, v <= N
1 <= valuei <= 100

My solution : Create a list of co-primes for each value from 1 to 100 (Precompute) Traverse the tree and for each node we maintain a hashmap of ancestors(value -> depth). When we visit a node it will contain the path from the root of the tree to this current node. We now traverse the list of co-primes for the current node and select the node that exists in the map as well in the precomputed list of the particular node(value) and select the value which has the maximum depth(closest ancestor).

However the time complexity of the solution per test case is O(N*valuei) which I think might not pass the problem. Can you please help with some optimized approach?