Tree Of Co Primes :
Difficulty Level : Medium
Submissions : 128
Asked In :
Marks :20
: 5 | : 0
There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of $$$N$$$ nodes numbered from $$$0$$$ to $$$N-1$$$ and exactly $$$N-1$$$ edges . Each node has a value associated with it i.e $$$nums[i]$$$ denote the value on node $$$i$$$, and the root of the tree is node $$$0$$$.
Two values $$$x$$$ and $$$y$$$ are coprime if $$$gcd(x, y)==1$$$ where $$$gcd(x, y)$$$ is the greatest common divisor of $$$x$$$ and $$$y$$$.
An ancestor of a node $$$i$$$ is any other node on the shortest path from node $$$i$$$ to the root. A node is not considered an ancestor of itself.
Output $$$N$$$ space-separated integers, where $$$i_{th}$$$ integer (0-based indexing) represents the closest ancestor to node $$$i$$$ such that $$$nums[i]$$$ and $$$nums[i_{th}]$$$ are coprime, or $$$-1$$$ if there is no such ancestor.
The first line contains a single integer $$$1\le N \le 10^{5}$$$.
The second line contains $$$N$$$ space separated integers where $$$0\le i < n$$$ integer denotes $$$1\le nums[i]\le 50$$$.
Following $$$N-1$$$ lines contains two space separated integers $$$u$$$ and $$$v$$$ which denotes $$$u$$$ and $$$v$$$ are connected by an edge.
Output $$$N$$$ space-separated integers, where $$$i_{th}$$$ integer (0-based indexing) represents the closest ancestor to node $$$i$$$ such that $$$nums[i]$$$ and $$$nums[i_{th}]$$$ are coprime, or $$$-1$$$ if there is no such ancestor.
4 2 3 3 2 0 1 1 2 1 3
-1 0 0 1
7 5 6 10 2 3 6 15 0 1 0 2 1 3 1 4 2 5 2 6
-1 0 -1 0 0 0 -1
