트리 고치기
시간 제한1초메모리 제한1024 MB
루트가 1번인 트리에서 M개의 고장 난 정점이 주어질 때, 고장 난 정점을 K개 이하로 고쳐서 작동하는 정점 수의 최댓값을 구한다.
문제
번 정점을 루트로 하고 개의 정점을 갖는 트리가 있다. 트리의 각 정점은 부터 까지의 서로 다른 정수로 번호가 매겨져 있다. 이 트리에는 개의 고장 난 정점이 있다. 고장 난 정점은 작동하지 않으며, 해당 정점의 자손 정점들도 고장 여부와 상관없이 작동하지 않는다. 즉, 어떤 정점의 조상들 중 고장 난 정점이 하나라도 있다면 그 정점은 작동하지 않는다.
주어진 트리에서 고장 난 정점을 개 이하로 고쳐서 작동하는 정점의 수를 최대로 만들어 보자.
입력
첫 번째 줄에 트리의 정점의 수 , 고장난 정점의 수 , 최대로 고칠 수 있는 정점의 수 가 공백으로 구분되어 주어진다.
두 번째 줄부터 줄에 걸쳐 트리의 간선을 이루는 서로 다른 두 정점 가 공백으로 구분되어 주어진다.
번째 줄에 개의 고장난 정점의 번호가 공백으로 구분되어 주어진다. 개의 정점의 번호는 모두 다르다.
출력
첫 번째 줄에 주어진 트리에서 고장 난 정점을 개 이하로 고쳐서 작동하는 정점의 수의 최댓값을 출력한다.