Not One

면접 대비

시간 제한1초메모리 제한1024 MB

요약

가중치가 있는 트리에서 노드 가중치의 최대공약수가 1이 아닌 가장 큰 연결 부분 트리의 크기를 구합니다.

난이도: 보통10점 중 5점
유형: 트리, 정수론, 유니온 파인드
정답자: 아직 제출이 없습니다

문제

양의 정수 집합 S의 최대공약수(GCD)는 S의 모든 원소를 나누는 가장 큰 양의 정수 d이다. 예를 들어 GCD(10) = 10, GCD(6, 9) = 3, GCD(20, 12, 16, 36) = 4이다.

N개의 노드로 이루어진 트리가 주어진다. 노드는 1부터 N까지 번호가 붙어 있고, 노드 i에는 양의 정수 가중치 A_i가 할당되어 있다. 노드들의 가중치 GCD가 1이 아닌 부분트리 중 가장 큰 크기를 구하라. 그런 부분트리가 없으면 0을 출력한다. 트리 T'는 T의 연결된 부분집합일 때만 T의 부분트리이다. 부분트리의 크기는 그 안에 있는 노드의 수이다.

아래 그림은 N = 7이고 A = {10, 5, 8, 6, 10, 6, 4}인 트리이다.

이 트리에서 GCD가 1이 아닌 부분트리는 15개이다. 크기가 1인 것이 7개, 2인 것이 4개, 3인 것이 3개, 4인 것이 1개이다. 가장 큰 부분트리는 4, 5, 6, 7번 노드로 이루어지며, 이들 가중치의 GCD는 GCD(A_4, A_5, A_6, A_7) = GCD(6, 10, 6, 4) = 2이다.

입력

첫 줄에 노드 수 N (2 ≤ N ≤ 100000)이 주어진다. 둘째 줄에는 i번 노드의 가중치 A_i (1 ≤ A_i ≤ 10^6) N개가 주어진다. 이어서 N-1개의 줄에 각각 간선으로 연결된 두 노드 u_j, v_j (1 ≤ u_j < v_j ≤ N)가 주어진다. 주어지는 트리는 연결되어 있다.

출력

가중치의 GCD가 1이 아닌 부분트리의 최대 크기를 한 줄에 출력한다. 그런 부분트리가 없으면 0을 출력한다.

예제3

예제 1

입력

7
10 5 8 6 10 6 4
1 2
2 3
2 4
4 5
4 6
4 7

예상 출력

예제 2
입력
```
4
1 1 1 1
1 2
2 3
3 4
```
예상 출력
```
0
```

예제 3

입력

5
100 100 100 100 100
3 4
1 2
3 5
2 4

예상 출력