시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 1024 MB 153 60 32 29.907%

문제

$N$개의 정점으로 구성된 가중치 없는 트리가 주어진다. 트리 상의 두 정점 사이의 거리는 두 정점 사이의 간선의 개수로 정의한다.

각 정점에는 수가 적혀 있으며, 적어도 두 정점은 같은 값임이 보장된다. 이때, 서로 같은 값이 쓰여 있는 두 정점 쌍 중 가장 거리가 가까울 때의 거리를 구해보자.

입력

첫째 줄에 트리의 정점의 개수 $N$이 주어진다. ($2 \leq N \leq 100\ 000$)

둘째 줄에 각 정점의 고유한 값인 정수 $c_1, c_2, \cdots, c_N$이 주어진다. ($1 \leq c_i \leq N$)

셋째 줄부터 $N - 1$개 줄에 걸쳐 각 줄마다 트리를 이루는 간선을 나타내는 정수 $u$와 $v$가 주어진다. 이는 $u$번 정점과 $v$번 정점을 잇는 간선이 존재함을 의미한다. ($1 \leq u, v \leq N$, $u \neq v$)

출력

서로 같은 값을 갖는 두 정점 쌍 중 가장 거리가 가까울 때의 거리를 출력한다.

예제 입력 1

7
1 2 3 1 4 2 2
1 2
1 3
3 4
3 5
4 6
5 7

예제 출력 1

2

출처

University > 서강대학교 > 2020 Sogang Programming Contest (Champion) G번