바로 과수원 정상화

테라와 루루는 오래된 과수원의 운반 시설을 정비하려고 한다.

과수원에는 $N$개의 사과 집하장이 있으며, $N-1$개의 양방향 운반 통로가 집하장들을 연결하고 있다. 전체 통로망은 트리 구조를 이룬다.

두 사람은 일부 집하장을 철거하고, 남은 집하장과 통로를 새로운 자동 포장 라인으로 사용하려 한다. 자동 포장 라인은 중간에 갈라질 수 없으므로, 정비가 끝났을 때 남아 있는 집하장들은 하나의 단순 경로를 이루어야 한다. 집하장이 하나만 남은 경우도 단순 경로로 본다.

집하장 $i$를 철거하지 않고 포장 라인에 포함하면 유지 가치 $b_i$를 얻는다. $b_i$는 음수일 수도 있다.

또한 각 통로에는 철거 방향에 따른 정비 손익이 정해져 있다. 집하장 $u$와 $v$를 잇는 통로에 대해,

• 집하장 $u$를 철거하고 설비를 $v$ 쪽으로 이전하면 $c_{u,v}$를 얻는다.
• 집하장 $v$를 철거하고 설비를 $u$ 쪽으로 이전하면 를 얻는다.

정비 손익은 음수일 수도 있다.

처음에는 모든 집하장과 통로가 남아 있다. 테라와 루루는 다음 작업을 원하는 만큼 수행할 수 있다.

1. 현재 정확히 하나의 통로와 연결된 집하장 $x$를 고른다.
2. $x$와 연결된 유일한 집하장을 $y$라 하자.
3. 집하장 $x$와 두 집하장을 잇는 통로를 철거하고, $c_{x,y}$를 얻는다.

정비 작업은 남아 있는 집하장들이 하나의 단순 경로를 이룰 때에만 끝낼 수 있다.

정비가 끝나면 남아 있는 모든 집하장 $i$에 대해 $b_i$를 얻는다.

테라와 루루가 얻을 수 있는 총 가치의 최댓값을 구하여라.

첫째 줄에 집하장의 수 $N$이 주어진다. ($1\le N\le200\,000$)

둘째 줄에 각 집하장의 유지 가치 $b_1,b_2,\ldots,b_N$이 공백으로 구분되어 주어진다. ()

테라와 루루가 얻을 수 있는 총 가치의 최댓값을 출력한다.