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