시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 4 4 100.000%

문제

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

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

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

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

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

입력

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

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

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

마지막 줄에는 점수 S0, S1, ..., SN-1이 주어진다. (-1,000 ≤ Si ≤ 1,000)

출력

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

예제 입력 1

4
0 1
0 3
1 2
0 1
0 3
3 2
1000 24 100 -200

예제 출력 1

1024

예제 입력 2

4
0 1
0 3
1 2
0 1
0 3
3 2
1000 24 100 200

예제 출력 2

1324

예제 입력 3

4
0 1
0 3
1 2
0 1
0 3
3 2
-1000 -24 -100 -200

예제 출력 3

0

예제 입력 4

4
0 1
0 3
1 2
0 1
0 3
3 2
-1000 24 100 200

예제 출력 4

200

힌트

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

출처