특별 노드

정점이 n(1 <= n <= 1,000)개인 루트 있는 트리 T가 주어진다. 각 정점 v에는 가중치 w_v(1 <= w_v <= 50,000)가 있고, 루트를 기준으로 볼 때 모든 정점의 가중치는 부모 정점의 가중치보다 크다.

각 정점은 특별 노드 또는 일반 노드 중 하나로 정한다. 루트는 반드시 특별 노드이다.

다시 계산한 가중치는 다음과 같이 정한다.

• 정점 v가 특별 노드이면, 새 가중치는 원래 가중치 w_v이다.
• 정점 v가 일반 노드이면, v의 가장 가까운 특별 조상 u에 대해 새 가중치는 w_v - w_u이다.

특별 노드들을 적절히 골라, 모든 정점의 새 가중치 합을 최소로 만들어라.

첫째 줄에 정점의 수 n과 루트 정점의 번호가 주어진다. 둘째 줄에 1번부터 n번까지 정점의 가중치가 공백으로 구분되어 주어진다. 다음 n-1개 줄에는 트리에서 서로 연결된 두 정점의 번호가 주어진다.

새 가중치 합의 최솟값을 출력한다.