https://www.acmicpc.net/problem/21759
접근법
- 팀을 subtree로 연결하는 아이디어
- 두 개의 팀의 팀장의 관계
- 팀장이 서로의 조상이 아닌 경우
- 한쪽이 다른 한쪽의 조상인 경우
- 부모노드에서 자식 노드를 연결하는 아이디어
- 자식 노드를 루트로 했을때의 값이 양수가 아니면? 연결할 필요가 없음
- 양수이면? 반드시 연결해야함(문제 조건 3)
- subtree에서 정답을 구하기 위해서 필요한 요소를 찾는 아이디어
- 요소1 : subtree의 루트를 포함하는 팀의 최대 값
- 요소2 : subtree 내부의 한 개 팀의 최대 값
- 요소3 : subtree 내부의 두 개 팀의 합의 최대값
- 요소4 : subtree가 조상과 연결되지 않았을때 자식중의 최대값
- 두 개의 팀중 한쪽이 다른 한쪽의 조상인 경우를 찾기 위해 필요
- 문제에서 주어진 케이스
- DFS, subtree 탐색을 끝낸 후 필요한 요소를 찾음
- 요소1 처리
- subtree 중 요소1이 양수인 것들을 더함
- 요소2 처리
- max(요소1, max(subtree의 요소2))
- 요소3 처리
- max(subtree(요소2들의 합), 요소1 + 요소4)
- 요소4를 위해 다음과 같이 처리
- subtree를 연결하는 경우 : subtree의 요소4를 후보로 선정
- subtree를 연결하지 않는 경우 : subtree의 max(요소4, 요소2 )
- 요소1 처리
newbieski