이동식 저장소

1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, 각 길은 방향성이 없어서 A번 마을에서 B번 마을로 갈 수 있다면 B번 마을에서 A번 마을로 갈 수 있다. 또, 모든 마을은 연결되어 있다. 두 마을 사이에 직접 잇는 길이 있을 때, 두 마을이 인접해 있다고 한다. 이 나라의 주민들에게 성취감을 높여 주 www.acmicpc.net 그래프에서 독립 집합은 다음과 같이 정의된다. 그래프의 모든 정점 V의 부분집합 S에 대하여, 임의의 S의 두 정점 사이를 연결하는 간선이 없을 때 S를 독립 집합이라고 한다. 독립 집합의 크기는 정점..