All Tracks Data Structures Trees Problem

GCD on Tree
Tag(s):

Algorithms, Hard, Regular expression, String, Trees

Problem
Editorial
Analytics

Given a tree with \(N\) vertices. Each vertex has a value \(a_i\). For vertex \(i\) and \(j\), if some vextex \(x\) is on the path between \(i\) and \(j\), and \(x\) is neither \(i\) nor \(j\), we update \(Ans_x=max(Ans_x,GCD(a_i,a_j))\)\(GCD\) means the greatest common divisor function. \(Ans\) is an array of \(N\) zeros initial.

Find the \(Ans\) array after all updation.

Input Format

First line contains an integer \(N(1\le N\le 10^5)\).

Second line contains \(N\) integers, represent the array \(a(1\le a_i\le 10^5)\).

Each of the next \(N-1\) lines contains two integers \(u,v\), represent an edge in the tree.

Output Format

\(N\) integers in one line, represent the array \(Ans\), separated by space.

SAMPLE INPUT
7
2 1 6 1 6 1 3
1 2
2 3
3 4
4 5
3 6
6 7
SAMPLE OUTPUT
0 2 3 6 0 3 0
Explanation

Vertex \(2\) is updated by \(1\) and \(5\),

Vertex \(3,6\) is updated by \(5\) and \(7\),

Vertex \(4\) is updated by \(3\) and \(5\),

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?