안 쓰던 블로그

www.acmicpc.net/problem/12995 트리나라는 n개의 도시로 이루어져 있고 각 도시 1~n은 모두 연결되어 있다 직원 k명이 전부 이사를 가야 하는데 모든 직원이 서로 다른 도시로 가야 해서 k개의 이사할 도시를 정해야 한다 k개의 도시는 모두 연결되어 있어야 한다 이사할 도시 k개를 고르는 방법의 수를 구하는 문제 k개 도시를 골라야 하면서 전부 연결되어 있어야 하니 다른 트리에서의 dp문제였던 트리의 독립집합이나 사회망 서비스와는 비슷하지만 다른 접근이 필요했다 예를 들어 k=15라고 하면 a, b서브트리에 13을 주고 c서브트리에 2를 줄 수도 있고 a에 2를 주고 b에 12를 주고 c에 1을 주는 방법도 있는 등 다양한 방법이 나올 수 있는데 이걸 어떻게 구현하느냐에 대한 문제였..