시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 512 MB25114411053.922%

문제

n개의 노드와 n - 1개의 간선으로 구성된 트리 T가 있다. 노드 번호는 0부터 n - 1까지이고 0번 노드가 루트이다. 간선에는 가중치가 없다. 트리 T에 있는 각 노드에는 하나의 정수가 적혀있다. 루트 노드에서 시작하여 이웃한 노드를 방문하면서 노드에 적혀있는 정수의 합을 최대로 하려고 한다. 노드를 방문하면 해당 노드에 적힌 정수는 무조건 더해야 한다. 같은 노드를 여러 번 방문할 수 있고, 여러 번 방문해도 최초 한 번만 해당 노드에 적혀있는 정수를 더한다. 루트 노드는 항상 방문해야 한다. 트리 T가 주어지면, 루트 노드에서 시작하여 이웃한 노드를 방문할 때 방문한 노드에 적혀있는 정수 합의 최댓값을 출력하자.

입력

첫 번째 줄에 노드의 수 n이 주어진다.

두 번째 줄부터 n - 1개 줄에 걸쳐 간선의 정보가 주어진다. 한 줄에 하나의 간선 정보가 주어진다. 하나의 간선 정보는 부모 노드 번호 p와 자식 노드 번호 c가 공백을 사이에 두고 순서대로 주어진다.

다음 줄에는 0번 노드부터 n - 1번 노드까지 노드에 적혀있는 n개의 정수가 공백을 사이에 두고 순서대로 주어진다. 즉, i번째 수는 i - 1번 노드에 적혀있는 정수를 의미한다.

출력

첫 번째 줄에 방문한 노드에 적혀있는 정수 합의 최댓값을 출력한다.

제한

  • 2 ≤ n ≤ 100,000
  • 0 ≤ p, cn - 1, pc
  • 간선들로 만들어진 그래프는 트리이다.
  • -100,000 ≤ 노드에 부여된 값 ≤ 100,000

예제 입력 1

8
0 1
0 2
1 3
1 4
2 5
2 6
6 7
1 -5 -10 -1 10 20 -5 20

예제 출력 1

31

노드 0, 노드 1, 노드 2, 노드 4, 노드 5, 노드 6, 노드 7을 방문하는게 정답이다.

출처