시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 1024 MB | 623 | 249 | 157 | 32.845% |
$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$)
서로 같은 값을 갖는 두 정점 쌍 중 가장 거리가 가까울 때의 거리를 출력한다.
7 1 2 3 1 4 2 2 1 2 1 3 3 4 3 5 4 6 5 7
2
University > 서강대학교 > 2020 Sogang Programming Contest > Champion G번
University > 서강대학교 > 2020 Sogang Programming Contest > Open G번