문제
어떤 특이한 개미종은, 방이 정점이고 터널이 간선인 개미굴을 만들고 각 방에 음식인 견과류를 저장한다.
이 종은 공기 흐름을 위해 견과류보다 살짝 큰 크기의 방을 만들고, 딱 맞는 크기의 터널을 만든다.
따라서, 공기 흐름을 위해 터널에는 견과류를 놔두면 안된다.
견과류가 있는 방에 들어가려면 터널을 통해 견과류를 인접한 방으로 밀어내야 한다.
개미가 나온 방 외에 다른 인접한 방이 비어 있지 않으면 견과류를 밀어낼 수 없으므로, 개미가 방에 들어갈 수 없다.
주어진 개미굴에 대하여, 개미들이 입구인 1번 정점으로부터 들어갈 수 있는 방의 개수를 구하여라.
개미가 처음에 있는 방(입구)에는 견과류가 없으며, 개미굴에는 사이클이 없음이 보장된다.
입력
첫 번째 줄에 굴의 개수인 N과 견과류가 존재하는 굴의 개수인 M이 공백으로 구분되어 주어진다.
다음 줄 부터 N-1개의 줄에 터널이 잇는 두 정점의 번호인 U와 V가 공백으로 구분되어 주어진다.
다음 줄부터 M개의 줄에 견과류가 존재하는 굴의 번호인 A가 주어진다.
- 1 <= N <= 200 000
- 0 <= M < N
- 1 <= U, V <= N
- U != V
- 1 <= A <= N
출력
첫 번째 줄에 개미들이 입구로부터 들어갈 수 있는 방의 개수를 출력하여라.
예제 #1
7 2
1 2
2 3
3 4
4 5
5 6
5 7
2
4
2
예제 #2
8 2
1 2
2 3
3 4
2 5
5 6
6 7
2 8
2
6
7
예제 #3
7 3
1 2
2 3
3 4
3 5
4 6
5 7
2
4
5
2
예제 #4
11 3
1 2
2 3
3 4
2 5
5 6
6 7
7 8
6 9
9 10
6 11
2
3
7
9
출처
Asia Yokohama Regional | dennisstar
로그인해야 코드를 작성할 수 있어요.