트리의 아름다움 - 구름LEVEL
트리의 아름다움
Quiz Info
트리의 아름다움
100points
Participant
16
Solved Rate
56.2%
2
1


준석이는 트리를 매우 좋아하여, 트리를 가지고 노는 것이 취미이다. 어느 날 준석이는 각 정점에 번호와 정수값이 적혀있는 트리를 가지고 놀던 중, 이 트리의 루트노드를 1번 노드라고 할 때 모든 정점의 아름다움을 점수로 표현해보고 싶어졌다. 이때, x번 노드의 점수는 루트노드부터 x번 노드까지 잇는 경로 상에 존재하는 모든 정수 값의 최대공약수이다. 이는 시작점인 루트노드의 정수값과 끝점인 x번 노드의 정수값도 포함하여 계산한다. 다음 트리를 통해 자세히 살펴보자.


루트노드인 1번 노드의 점수는 6이다. 2번 노드의 점수는 6과 4의 최대공약수인 2, 3번 노드의 점수는 6과 10의 최대공약수인 2, 4번 노드의 점수는 6, 10, 9의 최대공약수인 1, 5번 노드의 점수는 6, 10, 5의 최대공약수인 1이 된다. 준석이는 이렇게 점수를 계산하던 중 각 점수가 너무 작게 나오는 것이 영 마음에 들지 않았다. 그래서 각 노드의 점수를 계산할 때 임의의 한 노드의 정수값을 0으로 취급하여 점수를 좀 더 높이려 한다. 예를 들어, 2번 노드의 점수를 계산할 때 2번 노드의 정수값을 0으로 취급하면 6과 0의 최대공약수인 6을 얻을 수 있다. 마찬가지로 3번 노드의 점수를 계산할 때 1번 노드의 정수값을 0으로 취급하면 0과 10의 최대공약수인 10을 얻을 수 있다.

각 노드의 점수를 계산할 때 임의의 한 노드를 선택하여 정수값을 0으로 취급하여 계산할 수도 있고, 또는 주어진 트리를 그대로 사용하여 계산할 수도 있다. 이와 같은 방법으로 모든 노드에서의 최대 점수를 구하면 그 값은 얼마인지 계산하여라.


입력


첫째 줄에 트리를 구성하는 노드의 개수를 나타내는 정수 N이 주어진다.
(단, )

둘째 줄에 각 노드에 적혀있는 정수값 이 공백으로 구분되어 주어진다.
(단, 
)

이후 N-1줄에 걸쳐 두 정수 x, y가 공백으로 구분되어 주어진다. 이는 x번 노드와 y번 노드를 잇는 간선이 존재한다는 뜻이다.
(단, )


출력


첫째 줄에 N개의 정수 을 공백으로 구분하여 출력한다. 는 i번째 노드에서 계산될 수 있는 가장 큰 아름다움의 점수이다.



Input/Output Example
:
Blank
:
Line Break
:
Tab
Example 1
Input
5
641095
12
53
34
31
Output
661035
Example 2
Input
10
234567891011
12
23
34
45
56
67
48
89
910
Output
2321111111
Example 3
Input
4
6232
12
23
34
Output
6632
Example 4
Input
10
5578121488521205686
21
31
41
35
63
76
86
79
310
Output
557855551141412
⋇ Please keep the input and output formats carefully
Q & A
누구나 질문하고 답변할 수 있는 Q&A 게시판입니다.
다른 수강생들과 질문과 답변을 주고 받으며 함께 성장하세요!

Registered Questions (0)