12964번 - 점수의 합

N개의 정점으로 이루어진 트리 A와 B가 주어진다. 두 트리의 정점은 0번부터 N-1번까지 번호가 매겨져 있다.

0부터 N-1까지 각 정수에는 점수가 배정되어져 있다. 점수는 정수이며, i의 점수는 s[i]로 나타낸다.

아래와 같은 조건을 갖는 {0, 1, ..., N-1}의 부분 집합 S를 선택하는 프로그램을 작성하시오.

• 트리 A에서 S에 포함되어 있는 노드는 연결된 서브 그래프를 이루어야 한다.
• 트리 B에서 S에 포함되어 있는 노드는 연결된 서브 그래프를 이루어야 한다.

가능한 부분 집합 S중에서, 점수의 합이 최대가 되는 것을 구하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)

둘째 줄부터 N-1개의 줄에는 트리 A를 이루는 간선 a, b가 주어진다.

다음 N-1개의 줄에는 트리 B를 이루는 간선 c, d가 주어진다.

마지막 줄에는 정수의 점수가 0부터 N-1까지 주어진다. (-1,000 ≤ 점수 ≤ 1,000)

첫째 줄에 점수의 최댓값을 출력한다.

예제 1의 경우에 집합 {0, 1}을 선택하는 것이 점수의 합이 최대가 된다. {0, 1, 2}를 선택하면 트리 B가 연결된 서브 그래프가 아니다.