트리 고치기

시간 제한1초메모리 제한1024 MB

요약
루트가 1번인 트리에서 M개의 고장 난 정점이 주어질 때, 고장 난 정점을 K개 이하로 고쳐서 작동하는 정점 수의 최댓값을 구한다.
난이도

어려움10점 중 8점

유형
트리, 그리디, DFS
정답자
아직 제출이 없습니다

문제

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

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

입력

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

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

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

출력

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

예제1

  1. 예제 1

    입력
    12 5 2
    1 2
    1 3
    1 4
    2 5
    2 6
    2 7
    7 8
    7 9
    7 10
    4 11
    4 12
    2 4 5 7 8
    
    예상 출력
    7