'트리dp' 태그의 글 목록

tree dp는 최근에 코테에 나왔습니다. 그래서 트리 dp 2 문제를 준비해 보았습니다. 스크루지 민호 시리즈는 이들을 연습하기 좋은 셋트이기 때문입니다. 트리 탐색이나, dfs에 대한 기본적인 이해가 있다고 가정하고 진행하겠습니다. 먼저, 이 문제부터 보겠습니다. 왜 1부터 안 푸냐. 사실 해당 방법으로 풀기는 2가 1보다는 쉽기 때문입니다. 트리가 이렇게 있어요. 문제 조건을 잘 보시면, 양방향 간선에 연결되어 있는 도시 2개 중에 최소 하나 이상은 경찰서가 있어야 함을 알 수 있어요. 그러면 현재 cur에 경찰서를 세운 경우와 그렇지 않은 경우로 나눌 수 있음을 알 수 있어요. 먼저, cur에 경찰서를 세우지 않은 경우를 생각해 봅시다. 그러면, 자식 도시들은 모두 경찰서를 세워야 합니다. 만약에..