데이트

유담이와 우현이는 데이트하고 있다. 유담이는 우현이가 바람을 피우는 것을 걱정하여, 두 사람이 자주 다니는 장소들을 CCTV로 감시하려고 한다.

장소들의 연결 관계는 $N$개의 정점과 $N-1$개의 간선으로 이루어진 트리로 표현된다. 두 정점 $u,v$ 사이의 거리를 두 정점을 잇는 단순 경로에 포함된 간선의 개수로 정의한다.

각 정점 $v$에 음이 아닌 정수 $B_v$를 정한다.

• $B_v=0$이면 $v$번 정점에는 CCTV를 설치하지 않는다.
• $B_v\geq 1$이면 $v$번 정점에 감시 거리 $B_v$인 CCTV를 설치한다. 이 CCTV의 비용은 $B_v$이며, $v$와의 거리가 $B_v$ 이하인 모든 정점을 감시한다.

모든 정점이 하나 이상의 CCTV에 감시되도록 할 때, 설치한 CCTV들의 총비용 $\sum_{v=1}^{N} B_v$의 최솟값을 구하여라.

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

$N$ $u_1\ v_1$ $u_2\ v_2$ $\vdots$ $u_{N-1}\ v_{N-1}$

각 $i$ ($1\leq i\leq N-1$)에 대해 $u_i$번 정점과 $v_i$번 정점을 잇는 간선이 존재한다.

첫째 줄에 모든 정점을 감시하기 위한 총비용의 최솟값을 출력한다.

• $2\leq N\leq 500\,000$.
• $1\leq u_i,v_i\leq N$ ($1\leq i\leq N-1$).
• $u_i\neq v_i$ ($1\leq i\leq N-1$).
• 주어진 간선들은 트리를 이룬다.