트리 뽑아내기

루트가 없는 정점이 $N$개인 트리가 주어진다. 정점 $i$의 가중치는 $A_i$이다.

당신은 다음 연산을 원하는 만큼 수행할 수 있다.

• 현재 트리에 정점이 $2$개 이상 남아 있을 때, 리프 정점 하나를 고르고 해당 정점을 제거한다. 리프 정점은 현재 트리에서 차수가 $1$인 정점이다.

연산을 모두 마친 뒤 남은 정점들의 가중치 합을 최대화하여라.

입력은 다음과 같은 형식으로 주어진다.

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_{N-1}$ $v_{N-1}$

여기서 $u_k$와 $v_k$는 $k$번째 간선이 잇는 두 정점이다. $N=1$이면 간선은 주어지지 않는다.

연산을 모두 마친 뒤 남은 정점들의 가중치 합의 최댓값을 출력한다.

• $1 \le N \le 200\,000$
• $-10^9 \le A_i \le 10^9$
• $1 \le u_k,v_k \le N$
• 입력으로 주어지는 간선들은 트리를 이룬다.
• 모든 입력값은 정수이다.