6177 : 하중 분산 트리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
트리 형태로 연결된 구조물에서 각 노드가 갖는 자중 w와 지탱할 수 있는 최대 하중 L이 주어집니다. 각 노드는 자신을 루트로 하는 서브트리의 전체 무게 합(자신과 모든 자식들의 무게 합)을 지탱해야 합니다. 하중을 견디지 못하고 붕괴하는 노드가 발생하는지 조사하고, 발생한다면 가장 깊이가 깊은 붕괴 노드의 번호를 출력하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N-1개의 줄에 걸쳐 트리 간선 정보 u, v가 주어집니다.
그 다음 줄에 각 노드의 자중 w N개가 공백으로 구분되어 주어집니다.
그 다음 줄에 각 노드의 최대 허용 하중 L N개가 공백으로 구분되어 주어집니다.
둘째 줄부터 N-1개의 줄에 걸쳐 트리 간선 정보 u, v가 주어집니다.
그 다음 줄에 각 노드의 자중 w N개가 공백으로 구분되어 주어집니다.
그 다음 줄에 각 노드의 최대 허용 하중 L N개가 공백으로 구분되어 주어집니다.
출력 설명
붕괴하는 노드가 없다면 SAFE를 출력하고, 붕괴하는 노드가 존재한다면 해당 노드의 번호(여러 개라면 깊이가 가장 깊은 것, 깊이도 같다면 노드 번호가 작은 것)를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 2
1 3
2 4
2 5
10 20 30 40 50
200 150 100 50 50
출력 예시
COPY
복사되었습니다!
복사되었습니다!
SAFE