Good Influencers
면접 대비시간 제한1초메모리 제한1024 MB
각 정점이 처음에 참여 의사가 있는지와 비용이 주어지는 트리에서, 의사가 있는 정점을 선택해 이웃을 모두 참여 의사로 바꾸는 과정을 반복할 때 모든 정점을 참여시키는 최소 비용을 구한다.
문제
컴퓨터 과학 수업에 서로 다른 학번 1번부터 N번까지를 가진 N명(N ≥ 2)의 학생이 있다. 학생들 사이에는 N − 1개의 친구 관계가 있고, i번째 관계는 학생 Ai와 Bi를 잇는다(Ai ≠ Bi, 1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N). 수업의 모든 학생 쌍은 서로 친구이거나 사회적으로 연결되어 있다. 두 학생 a와 b가 사회적으로 연결되어 있다는 것은 다음을 만족하는 학생 집합 m1, m2, . . . , mk가 존재한다는 뜻이다.
- a와 m1은 친구이다.
- mi와 mi+1은 친구이다 (1 ≤ i ≤ k − 1).
- mk와 b는 친구이다.
처음에 각 학생 i는 CCC를 칠 의향이 있거나(Pi가 Y인 경우) 칠 의향이 없다(Pi가 N인 경우). 처음에 적어도 한 학생은 CCC를 칠 의향이 있고, 적어도 한 학생은 칠 의향이 없다.
CCC는 몇몇 학생에게 돈을 주고 CCC의 인플루언서로 활동하게 하려고 예산을 배정했다. CCC는 CCC를 칠 의향이 있는 학생 i를 한 명 골라 Ci달러를 지급하고, 그 학생에게 자신의 모든 친구를 대상으로 세미나를 열게 한다. 그러면 그 친구들은 모두 CCC를 칠 의향이 있게 된다.
CCC가 모든 학생이 CCC를 칠 의향이 있게 만들기 위해 필요한 최소 비용을 구하도록 돕자.
입력
첫째 줄에 정수 N이 주어진다.
다음 N − 1개 줄에는 각각 공백으로 구분된 두 정수 Ai와 Bi가 주어진다(1 ≤ i ≤ N − 1).
다음 줄에는 Y 또는 N으로 이루어진 N개의 문자 P1 . . . PN이 주어진다.
다음 줄에는 공백으로 구분된 N개의 정수 C1 . . . CN이 주어진다.
출력
모든 학생이 CCC를 칠 의향이 있게 만드는 데 필요한 최소 달러 금액을 정수로 출력한다.