만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

트리 고치기

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

요약
루트가 있는 트리에서 고장 난 정점 중 최대 K개를 수리하여 작동하는 정점의 수를 최대화하는 문제입니다. 정점은 조상 중 고장 난 정점이 없어야 작동합니다.
난이도

보통10점 중 6점

유형
트리, 동적 계획법, 정렬
정답자
아직 제출이 없습니다

문제

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

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

입력

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

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

N+1N+1번째 줄에는 고장 난 정점의 번호 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