23044번 - 트리 조각하기

문제

타고난 트리 조각가 온조는 오늘도 완벽한 작품을 만들기 위해서 트리 $T$를 준비하였다. 온조는 뛰어난 예술적 직관을 통해 조각할 작품을 머릿속으로 구상하였고, 먼저 조각상의 전체적인 틀을 잡기 위해서 $T$에서 제거할 정점들을 결정하였다.

그런데 $T$의 정점들은 매우 단단하기 때문에 일반적인 도구로는 제거할 수가 없고, 폭탄을 사용하여 제거해야 한다. 그래서 온조는 $T$의 몇몇 정점에 폭탄을 설치한 뒤 한 번에 폭발시키는 방법을 사용하려고 한다. 모든 폭탄의 세기는 양의 정수인 $p$로 같으며, 모든 폭탄이 폭발하고 난 후 폭탄이 설치된 정점과의 거리가 $p$ 미만인 정점들은 제거된다. 이 과정에서 제거해야 할 정점이 제거되지 않거나 제거하지 않아야 할 정점이 제거되면 작품이 망가지기 때문에, 온조는 이런 일이 일어나지 않도록 폭탄을 설치할 것이다.

온조는 폭발 과정도 작품의 한 부분이기 때문에 폭탄의 세기 $p$가 크면 클수록 작품의 예술적 가치가 높아진다고 생각한다. 트리 $T$와 제거해야 할 정점들이 주어지면 폭탄의 세기 $p$로 가능한 값 중 최댓값을 구해서 온조를 도와주자. 모든 정점을 제거해야 하는 경우나 모든 정점을 제거하지 않아야 하는 경우는 주어지지 않는다.

입력

첫째 줄에 트리 $T$를 구성하는 정점의 개수 $N$이 주어진다. (2ドル \le N \le 200,000円$)

둘째 줄에 $N$개의 수 $C_i$가 공백을 사이에 두고 주어진다. $C_i$는 0ドル$ 또는 1ドル$이다. $C_i=1$인 경우 $i$번 정점을 제거해야 한다는 의미이며, $C_i=0$인 경우 $i$번 정점을 제거하지 않아야 한다는 의미이다.

셋째 줄부터 $(N-1)$개 줄에 걸쳐 간선 정보가 주어지며, 각 줄에는 하나의 간선이 잇는 두 정점의 번호 $u,ドル $v$가 공백을 사이에 두고 주어진다. (1ドル \le u \le N,ドル 1ドル \le v \le N,ドル $u \ne v$)

출력

첫째 줄에 폭탄의 세기 $p$로 가능한 값 중 최댓값을 출력한다.

제한

힌트