32389번 - 트리 고치기

문제

1ドル$번 정점을 루트로 하고 $N$개의 정점을 갖는 트리가 있다. 트리의 각 정점은 1ドル$부터 $N$까지의 서로 다른 정수로 번호가 매겨져 있다. 이 트리에는 $M$개의 고장 난 정점이 있다. 고장 난 정점은 작동하지 않으며, 해당 정점의 자손 정점들도 고장 여부와 상관없이 작동하지 않는다. 즉, 어떤 정점의 조상들 중 고장 난 정점이 하나라도 있다면 그 정점은 작동하지 않는다.

주어진 트리에서 고장 난 정점을 $K$개 이하로 고쳐서 작동하는 정점의 수를 최대로 만들어 보자.

입력

첫 번째 줄에 트리의 정점의 수 $N(1\leq N\leq 10^5),ドル 고장난 정점의 수 $M(1\leq M\leq N),ドル 최대로 고칠 수 있는 정점의 수 $K(1\leq K\leq 10)$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N-1$줄에 걸쳐 트리의 간선을 이루는 서로 다른 두 정점 $u,v(1\leq u,v\leq N)$가 공백으로 구분되어 주어진다.

$N+1$번째 줄에 $M$개의 고장난 정점의 번호가 공백으로 구분되어 주어진다. $M$개의 정점의 번호는 모두 다르다.

출력

첫 번째 줄에 주어진 트리에서 고장 난 정점을 $K$개 이하로 고쳐서 작동하는 정점의 수의 최댓값을 출력한다.

제한

힌트