문제 제목 : 트리
문제 링크 : https://www.acmicpc.net/problem/13306

출처 : Olympiad > 한국정보올림피아드 > KOI 2016 > 중등부 3번

입력

맨 처음에는 트리의 정점의 개수 N과 쿼리의 개수 Q가 주어진다. 이후 N-1개의 줄에 각 정점에 부모 정점이 주어진다. 이후 (N-1)+Q개의 줄에 N-1개의 정점을 자르는 쿼리와 Q개가 섞여서 들어온다.

문제 이해

따라서 정점을 자르는 N-1개의 쿼리가 모두 실행되고 나면 모든 정점이 끝어져서 독립적으로 존재하는 그래프가 만들어진다.

따라서 입력에 주어지는 순서대로 정점을 분리하는 것 대신에 쿼리를 역으로 수행해서 정점을 붙여주는 동작을 Union-Find를 이용해서 풀면 더 빠르게 구현할 수 있습니다.

코드

코드 : github