13341번 - 두 트리

정점의 개수가 N개인 두 트리가 주어진다. 트리의 각 노드는 0부터 N-1까지 번호가 매겨져 있다.

i번 정점의 점수는 S_i이다.

집합 {0, 1, ..., N-1}의 부분 집합을 골라서 부분 집합에 포함되어 있는 정점의 점수의 합의 최댓값을 구하는 프로그램을 작성하시오. 이때, 다음과 같은 두 조건을 만족해야 한다.

• 첫 번째 트리에서 부분 집합에 포함되어 있는 정점끼리 연결 서브 그래프를 만들어야 한다.
• 두 번째 트리에서 부분 집합에 포함되어 있는 정점끼리 연결 서브 그래프를 만들어야 한다.

두 조건을 만족시키는 부분 집합 중에서 정점의 점수가 가장 큰 것을 구하는 프로그램을 작성하시오.

첫째 줄에 정점의 개수 N (2 ≤ N ≤ 50)이 주어진다.

둘째 줄부터 N-1개 줄에는 첫 번째 트리의 간선 정보가 주어진다.

그 다음 N-1개 줄에는 두 번째 트리의 간선 정보가 주어진다.

마지막 줄에는 점수 S₀, S₁, ..., S_N-1이 주어진다. (-1,000 ≤ S_i ≤ 1,000)

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

{0, 1}을 고르면 두 트리에서 모두 연결된 서브 그래프를 만든다. {0, 1, 2}는 두 번째 트리에서 0에서 2로 이동할 수 없다.