특별 노드
시간 제한2초메모리 제한128 MB
부모보다 자식의 가중치가 항상 큰 루트 트리에서 정점을 특별하거나 일반으로 지정해, 일반 정점의 가중치에서 가장 가까운 특별 조상의 가중치를 뺀 값들의 합을 최소화합니다.
문제
정점이 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개 줄에는 트리에서 서로 연결된 두 정점의 번호가 주어진다.
출력
새 가중치 합의 최솟값을 출력한다.