트리 뽑아내기

리프 정점을 제거하는 연산을 반복하면, 남아 있는 정점들은 항상 연결되어 있다. 반대로 트리의 임의의 연결 부분트리를 하나 정하면, 그 밖의 정점들은 바깥쪽 리프부터 제거하여 모두 없앨 수 있다.

따라서 문제는 가중치 합이 최대인 연결 부분트리를 찾는 문제와 같다.

트리를 정점 $1$을 루트로 잡아 생각하자. $dp_u$를 정점 $u$를 포함하고, $u$의 서브트리 안에서만 고르는 연결 부분트리의 최대 가중치 합이라고 하자.

자식 $v$에 대해 $dp_v$가 양수라면 $v$ 쪽 부분트리를 붙이는 것이 이득이고, $dp_v$가 음수라면 붙이지 않는 것이 이득이다. 따라서 다음 점화식이 성립한다.

$$dp_u=A_u+\sum_{v:\,v\text{는 }u\text{의 자식}}\max(0,dp_v)$$

정답은 모든 정점 $u$에 대한 $dp_u$의 최댓값이다. 모든 가중치가 음수일 수도 있으므로, 정답을 $dp_1$만으로 두면 안 되고 모든 정점에서 최댓값을 보아야 한다.

정답의 절댓값은 $32$비트 정수 범위를 넘을 수 있으므로 $64$비트 정수를 사용해야 한다.

시간 복잡도는 $O(N)$이다.