바리케이드

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

요약

트리에서 각 크기 k마다 정확히 k개의 정점을 가진 연결 성분이 만들어지고 그 성분을 나가는 간선이 없도록 자르는 최소 간선 수를 구한다.

난이도: 보통10점 중 7점
유형: 트리, 동적 계획법, DFS, 구현
정답자: 아직 제출이 없습니다

문제

바이트랜드(Byteland)는 양방향 도로로 연결된 여러 도시로 이루어진 섬이다. 도로망은 임의의 두 도시 사이를 잇는 경로가 (되돌아가지 않는 한) 정확히 하나만 존재하도록 만들어져 있다. 즉, 도시와 도로는 하나의 트리를 이룬다.

어려운 시기가 닥쳐, 바이트랜드는 전쟁을 준비하고 있다. 수석 전략가는 일부 도로에 바리케이드를 설치하여 특별 보안 구역(special security zone)을 만들려고 한다. 바리케이드가 설치된 도로로는 아무도 지나갈 수 없다. 이 구역이 안전하려면 다음 조건을 모두 만족해야 한다.

구역 안의 모든 도시에서 구역 안의 다른 모든 도시로 이동할 수 있어야 한다.
구역 밖의 도시에서 구역 안의 도시로는 이동할 수 없어야 한다.
구역은 정확히 $k$ 개의 도시로 이루어져야 한다.

여러 개의 $k$ 값에 대해, 정확히 $k$ 개의 도시로 이루어진 특별 보안 구역을 만들기 위해 최소한 몇 개의 도로에 바리케이드를 설치해야 하는지 구하여라.

도로망과 질의 목록을 입력받아, 각 질의마다 요구된 크기의 특별 보안 구역을 만드는 데 필요한 최소 바리케이드 수를 표준 출력에 출력하는 프로그램을 작성하여라.

입력

첫째 줄에 도시의 수 $n$ ( $1 \le n \le 3000$ )이 주어진다. 도시는 $1, 2, \ldots, n$ 번으로 번호가 매겨져 있다.

다음 $n - 1$ 개의 줄에는 각각 공백 하나로 구분된 두 정수 $a$ , $b$ ( $1 \le a, b \le n$ )가 주어지며, 도시 $a$ 와 도시 $b$ 를 직접 잇는 도로를 나타낸다. 임의의 두 도시는 최대 하나의 직접 도로로 연결된다.

그다음 줄에는 질의의 수 $m$ ( $1 \le m \le n$ )이 주어진다. 이어지는 $m$ 개의 줄에는 각각 하나의 정수 $k_i$ ( $1 \le k_i \le n$ )가 주어진다. $i$ 번째 질의는 정확히 $k_i$ 개의 도시로 이루어진 특별 보안 구역을 요구한다.

출력

정확히 $m$ 개의 줄을 출력한다. $i$ 번째 줄에는 다음을 출력한다.

정확히 $k_i$ 개의 도시로 이루어진 특별 보안 구역을 만들 수 없으면 $-1$ .
그렇지 않으면, 그러한 구역을 만들기 위해 바리케이드를 설치해야 하는 도로의 최소 개수.

예제2

예제 1
입력
```
7
1 2
1 3
2 4
2 5
3 6
3 7
2
2
3
```
예상 출력
```
2
1
```
예제 2
입력
```
2
1 2
2
1
2
```
예상 출력
```
1
0
```