거북이 원로

면접 대비

시간 제한5초메모리 제한256 MB

요약

안전한 출발 섬과 도착 섬을 골라 경로에 속한 섬들의 수명 변화량 합이 가장 커지는 경우를 구합니다.

난이도: 보통10점 중 4점
유형: 트리, 동적 계획법
정답자: 아직 제출이 없습니다

문제

N개의 섬이 나무처럼 연결되어 있고, 각 섬 i를 밟으면 수명이 $X_i$ 일만큼 변한다. 위험 동물이 있는 섬에는 착륙하거나 신호탄을 쏠 수 없다. 신호탄은 한 번뿐이므로 들어갈 섬과 나올 섬을 안전한 섬에서만 선택할 때, 늘릴 수 있는 수명의 최댓값을 구하라. 최댓값이 0 이하이면 Stay Home을 출력한다.

입력

첫 줄에 테스트케이스 수 $T$ ( $T \le 10$ )가 주어진다. 각 테스트케이스마다 섬 수 $N$ , $N-1$ 개의 다리, 길이 $N$ 의 $X_i$ 배열, 길이 $N$ 의 안전 여부 배열이 주어진다.

출력

최대 수명 연장 일수를 출력하거나, 0 이하이면 Stay Home을 출력한다.

예제1

예제 1

입력

2
3
1 2
2 3
5 20 -10
1 0 1
4
1 2
2 3
3 4
-1 5 -20 -1
1 0 0 1

예상 출력

15
Stay Home