문제
구름이는 트리를 매우 좋아하여, 트리를 가지고 노는 것이 취미이다. 어느 날 구름이는 각 정점에 번호와 정수값이 적혀있는 트리를 가지고 놀던 중, 이 트리의 루트 노드를 번 노드라고 할 때 모든 정점의 아름다움을 점수로 표현해보고 싶어졌다.
번 정점의 아름다움 점수는, 루트 노드부터
번 노드까지를 잇는 경로 상에 존재하는 모든 정수 값의 최대공약수이다. 이때 시작점인 루트 노드의 정수값과 끝점인
번 노드의 정수값도 포함하여 계산한다.
예제 1이 나타내는 트리를 통해 자세히 살펴보자.
- 루트 노드인 1번 노드의 점수는 6이다.
- 2번 노드의 점수는 6과 4의 최대공약수인 2이다.
- 3번 노드의 점수는 6과 10의 최대공약수인 2이다.
- 4번 노드의 점수는 6, 10, 9의 최대공약수인 1이다.
- 5번 노드의 점수는 6, 10, 5의 최대공약수인 1이다.
구름이는 이렇게 점수를 계산하던 중, 각 노드의 점수가 너무 작게 나오는 것이 마음에 들지 않았다. 그래서 각 노드의 점수를 계산할 때, 계산에 포함되는 노드들 중에서 임의의 노드 하나의 정수값을 으로 취급하여 점수를 좀 더 높이려 한다.
예를 들어, 2번 노드의 점수를 계산할 때 2번 노드의 정수값을 0으로 취급하면 6과 0의 최대공약수인 6을 얻을 수 있다. 마찬가지로 3번 노드의 점수를 계산할 때 1번 노드의 정수값을 0으로 취급하면 0과 10의 최대공약수인 10을 얻을 수 있다.
각 노드의 점수를 계산할 때 임의의 한 노드를 선택하여 정수값을 0으로 취급하여 계산할 수도 있고, 주어진 트리를 그대로 사용하여 계산할 수도 있다. 이와 같은 방법으로 모든 노드에 대해 각각 최대 점수를 구했을 때, 그 값들을 출력하시오.
입력
첫째 줄에 트리를 구성하는 노드의 개수를 나타내는 정수 이 주어진다.
둘째 줄에 각 노드에 적혀있는 정수값 이 공백을 두고 주어진다.
그 다음 줄에 걸쳐 두 정수
가 공백을 두고 주어진다. 이는
번 노드와
번 노드를 잇는 간선이 존재한다는 뜻이다.
- 입력으로 주어지는 모든 수는 정수이다.
출력
첫째 줄에 개의 정수
을 공백을 두고 출력한다.
는
번째 노드에서 계산될 수 있는 가장 큰 아름다움의 점수이다.