서로 껄끄럽지 않은 회식 명단
레벨 M4 · 코딩 · JavaScript · 목표 시간 22분 · 게시일 2026-10-27
회사 사람 n명(0번부터 n-1번)의 관계가 간선 n-1개짜리 트리 edges([u, v]는 u와 v가 직속 상하 관계라는 뜻)로 주어진다. 회식에 i번 사람을 부르면 즐거움 joy[i]가 생기지만, 간선으로 바로 이어진 두 사람을 함께 부를 수는 없다. 부를 사람을 골랐을 때 즐거움 합의 최댓값을 구하시오.
n은 1 이상 100,000 이하, joy[i]는 1 이상 1,000 이하이다. 트리가 한 줄로 길게 늘어설 수 있으니 깊은 재귀는 피하시오.
예제
solve(5, [[0,1],[0,2],[1,3],[1,4]], [3,4,5,1,1]) solve(1, [], [9]) solve(3, [[0,1],[1,2]], [1,5,1])