외곽 순환 도로 2

시간 제한: 2000 ms. 메모리 제한: 1024 MB.

KOI 도시는 $N$개의 교차로와 $N - 1$개의 양방향 도로로 이루어져 있으며, 임의의 두 교차로를 도로만 사용하여 오갈 수 있다. 즉, 도시의 도로망은 트리 구조이다. 도로는 $2$차원 평면 위에 있으며, 두 도로는 끝점을 제외한 위치에서 교차하지 않는다. 각 도로에는 $0$ 이상의 정수 가중치가 있다.

KOI 도시는 몇십 년 전까지만 해도 작은 마을이었으나, 사람이 유입되고 규모가 커지면서 급격히 팽창하였다. 팽창 과정에서 시장은 행정 편의를 위해 교차로에 $0$ 이상 $N - 1$ 이하의 번호를 붙였다. 이 번호 체계는 다음 성질을 만족한다.

• $0$번 교차로는 도시의 중심이며, 2개 이상의 도로와 인접함이 보장된다.
• 교차로 번호는 $0$번 교차로를 루트로 한 트리의 전위 순회(Preorder) 순서 중 하나이다.
• 모든 교차로에 대해, 도로로 직접 연결된 인접 교차로 중 번호가 가장 작은 교차로를 기준으로 하여 그 교차로에 인접한 교차로들을 반시계 방향으로 나열하면, 번호가 증가한다.

KOI 도시에 사람이 많이 유입되면서 교통 체증이 심해졌다. 시장은 이를 줄이려고 교통 인프라가 가장 빈약한 지역들을 외곽 순환 도로로 이었다. 도로를 정확히 1개만 가진 교차로들의 번호를 오름차순으로 나열한 리스트를 $\{V[0], V[1], \dots, V[K - 1]\}$라고 하자. 시장은 모든 $0 \le i \le K - 1$에 대해 $V[i]$번 교차로와 $V[(i + 1) \bmod K]$번 교차로를 잇는 양방향 도로를 건설하였다. 각 도로의 가중치는 $0$ 이상의 정수 $W[i]$이다. 번호 체계의 특성상, 두 도로가 끝점 이외의 위치에서 교차하지 않도록 외곽 순환 도로를 이을 수 있다는 점을 눈여겨보면 좋다.

KOI 도시를 거점으로 하는 범죄단 Dlalswp는 시민들에게 큰 피해를 주고 있다. 시장은 Dlalswp 범죄단을 잡기 위해 정보요원들을 투입하였다. 정보요원들의 첩보에 따르면, Dlalswp 범죄단은 길이가 홀수인 단순 사이클을 범죄 영역으로 삼고, 그 사이클을 돌면서 범죄를 저지른다.

악명 높은 Dlalswp 범죄단을 검거하기 위해, 시장은 길이가 홀수인 모든 단순 사이클에 경찰이 배치된 도로가 하나 이상 포함되도록 KOI 도시의 도로에 경찰을 배치하려고 한다. 도로에 경찰을 배치하는 데 드는 비용은 그 도로의 가중치와 같다. 시장이 목표를 이루는 데 필요한 최소 비용을 구하여라.

제한

• $4 \le N \le 100\,000$
• 모든 $i$에 대해 $0 \le P[i] \le i$ ($0 \le i \le N - 2$)
• 모든 $i$에 대해 $0 \le C[i] \le 10^{12}$ ($0 \le i \le N - 2$)
• 모든 $i$에 대해 $0 \le W[i] \le 10^{12}$ ($0 \le i \le K - 1$)