선로 간격
시간 제한2초메모리 제한512 MB
잎이 고정된 궤간을 가진 외국 역인 트리에서 국내 역의 궤간을 정해 각 간선의 절댓값 차이 합을 최소로 만들고, 그 최솟값의 내림을 출력한다.
문제
어떤 면에서 베이토치아는 꽤 뒤처진 나라이다. 국경을 맞댄 나라들은 모두 철도를 오래전부터 갖고 있는데, 베이토치아에는 아직 철도가 없다. 이대로 둘 수는 없다!
새로 세워진 베이토치아 국영 철도의 수석 기술자 바이타자르는 철도망을 설계했다. 이 철도망은 베이토치아 안의 여러 역과 국경 밖의 여러 역을 연결한다. 각 철도 연결은 두 역 사이를 잇고 양방향이다. 철도망의 어느 역에서든 다른 역으로 가는 방법은 정확히 하나뿐이며, 그 경로에서 같은 역을 두 번 지나지 않는다.
문제는 국경을 맞댄 모든 나라가 각자의 선로 간격 표준을 도입했다는 점이다. 게다가 베이토치아 국경 밖의 어느 역에서도 선로 간격을 바꿀 수 없다. 그래서 기술자 바이타자르는 다음과 같이 정했다. 베이토치아 전체에 공통된 선로 간격 표준을 두지 않고, 베이토치아의 역마다 선로 간격이 달라도 된다. 대신 역 사이의 철도 연결에는 BAZRK(베이토치아 자동 바퀴 간격 변경) 시스템을 설치해서, 운행 중에 열차 바퀴 간격을 바꿀 수 있게 한다.
BAZRK 시스템은 당연히 꽤 비싼 해법이다. 연결된 두 역의 선로 간격이 각각 r1, r2 비토미터라면, 두 역을 잇는 선로에 BAZRK 시스템을 설치하는 비용은 |r1 − r2| 메가바이탈라르이다.
바이타자르가 베이토치아의 각 역에 선로 간격을 적절히 정해서 BAZRK 시스템의 총비용을 최소로 만들도록 도와주자.
입력
첫째 줄에 두 정수 n과 m(2 ≤ n ≤ 500 000, 1 ≤ m ≤ n)이 주어진다. n은 철도망에 있는 전체 역(베이토치아 역과 외국 역을 모두 포함)의 수이고, m은 외국 역의 수이다. 외국 역에는 1부터 m까지의 번호가, 베이토치아 역에는 m + 1부터 n까지의 번호가 붙는다.
다음 n − 1개 줄에 역 사이의 철도 연결이 주어진다. 이 중 i번째 줄에는 두 정수 ui, vi(1 ≤ ui, vi ≤ n, ui ≠ vi)가 주어지며, 번호가 ui인 역과 vi인 역 사이에 직접적인 철도 연결이 있다는 뜻이다. 모든 외국 역은 정확히 다른 한 역과 연결되어 있고, 모든 베이토치아 역은 적어도 두 개의 다른 역과 연결되어 있다.
다음 m개 줄에는 외국 역의 선로 간격이 주어진다. 이 중 i번째 줄에는 정수 ri(1 ≤ ri ≤ 500 000)가 주어지며, 번호가 i인 외국 역의 선로 간격(비토미터)이라는 뜻이다.
출력
첫째 줄에 설치한 BAZRK 시스템의 총비용으로 가능한 최솟값을 메가바이탈라르 단위로 출력한다. 값은 가장 가까운 정수로 내림한다.