시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 14 9 6 85.714%

문제

준표는 던전을 클리어하고자 한다. 던전은 트리구조이며, 던전을 클리어하기 위해선 보스방에 사는 던전의 보스를 죽여야 한다. 보스방은 언제나 1번 정점에 있다.

보스방을 제외한 던전의 모든 단말정점에는 던전에 입장할 수 있는 입구가 있으며, 보스방에 들어가는 문은 유일하다. 즉 1번 정점에는 오직 하나의 간선만이 연결되어있다.

던전에는 보스 외에도 몬스터가 산다. 던전의 각 방마다 최대 한 마리의 몬스터가 서식할 수 있고, 준표가 보스방에 도달하기 위해선 경로를 막고있는 몬스터를 모두 죽여야 한다.

<그림 1> 던전의 예시

보스를 제외한 몬스터들은 던전에서 하나의 군집을 이루고 있어 던전의 연속된 일부분을 차지하고 있다.

<그림 2> 예제 1의 가능한 군집들. 빨간 사각형의 군집은 던전의 연속된 일부분을 차지하지 않아 있을 수 없는 군집이다.

준표에게는 무시무시한 병기가 있는데, g번 바이러스를 사용하면 유전자 g를 가지는 모든 몬스터들을 죽일 수 있는 생화학 병기다.

각 몬스터의 유전자는 하나의 양의 정수로 나타낼 수 있으며, 유전자 g를 가진다는 의미는 몬스터의 유전자가 g로 나누어떨어진다는 뜻이다.

즉, 죽이고자 하는 몬스터들의 "유전자의 공약수" 번 바이러스를 사용하면 모든 몬스터가 죽는다.

당연하지만 모든 유전자는 1로 나누어떨어지기 때문에 1번 바이러스를 사용하면 모든 몬스터를 죽일 수 있을 것이다.

하지만 번호가 낮을수록 가격이 비싸기 때문에 준표는 가능하면 가장 높은 번호의 바이러스를 사용한다. 즉, 준표는 죽이고자 하는 몬스터들의 "유전자의 최대공약수" 번 바이러스를 사용한다.

준표가 어떤 군집의 던전을 클리어하기 위해 사용하는 바이러스 번호를 치트키라고 하자. 준표는 가능한 모든 군집의 치트키의 총합을 구하고자 한다.

입력

첫 줄에 던전의 크기 N이 입력된다. (2 ≤ N ≤ 100,000)

두 번째 줄에 던전의 i번 방에 서식할 수 있는 몬스터의 유전자 gi 가 순서대로 입력된다. (1 ≤ gi ≤ 1,000,000,000)

세 번째 줄부터 N - 1줄에 걸쳐 던전의 구조가 u v 형태로 입력된다. 이는 u번 방과 v번 방을 잇는 통로가 있다는 의미이다. (1 ≤ u, v ≤ N)

출력

각 입구에서 출발했을 때 가능한 모든 군집의 치트키의 총합을 공백으로 구분하여 정점 번호순으로 출력한다.

매우 큰 수가 될 수 있으므로 109+7 로 나눈 나머지로 출력한다.

예제 입력 1

4
12 3 6 9
1 2
2 3
2 4

예제 출력 1

42 39

<그림 3> 예시 설명을 위한 가능한 모든 경우의 군집

3번 노드를 통해 입장한다면, 3번 노드에서 1번 노드로 가는 경로 중 색칠된 노드들의 최대공약수를 구해 모두 더한다.

그림 순서대로 gcd(12) = 12, gcd(12, 6) = 6, gcd(12) = 12, gcd(12, 3) = 3, gcd(12, 3, 6) = 3, gcd(12, 3) = 3, [불가능], gcd(12, 3, 6) = 3 으로 모두 더하면 42 이다.

4번 노드를 통해 입장할 때 역시 같은 방법으로 계산해보면

그림 순서대로 gcd(12) = 12, gcd(12) = 12, gcd(12, 9) = 3, gcd(12, 3) = 3, gcd(12, 3) = 3, gcd(12, 3, 9) = 3, [불가능], gcd(12, 3, 9) = 3 으로 모두 더하면 39 이다.

예제 입력 2

10
849745362 398947134 290474894 560506281 817809495 14794340 240257566 785198582 646030968 647292332
2 9
2 8
5 1
9 10
10 6
7 9
5 10
3 9
4 10

예제 출력 2

948217708 145161902 145161927 948217708 248727007

출처

University > 경인지역 6개대학 연합 프로그래밍 경시대회 > shake! 2020 H번