어떤 공항의 통로 구조는 \(N\)개의 구역과 이들을 잇는 \(N-1\)개의 통로로 이루어져 있으며, 전체가 하나로 연결된 트리 구조이다. 구역 \(i\)에 보안 카메라를 설치하면 \(w_i\)만큼의 감시 가치를 얻는다.

다만 서로 통로로 직접 연결된 두 구역에 동시에 카메라를 설치하면 화면이 겹쳐 비효율적이다. 따라서 인접한 두 구역에는 카메라를 동시에 설치할 수 없다. 이 조건을 지키면서 얻을 수 있는 감시 가치의 합의 최댓값을 구하여라.

\(1 \le N \le 200{,}000\)

\(1 \le w_i \le 10{,}000\)

주어지는 그래프는 트리이다.

첫째 줄에 구역의 수 \(N\)이 주어진다.

둘째 줄에 \(N\)개의 정수 \(w_1, w_2, \dots, w_N\) (\(1 \le w_i \le 10{,}000\))이 주어진다.

다음 \(N-1\)개의 줄에 각각 두 정수 \(a\), \(b\) (\(1 \le a, b \le N\))가 주어지며, 구역 \(a\)와 \(b\)가 통로로 연결되어 있음을 뜻한다. 주어지는 그래프는 트리이다.

설치할 수 있는 카메라들의 감시 가치 합의 최댓값을 출력한다.

riseoj 작성

출처 Original