시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 25 | 16 | 15 | 62.500% |
Byteland is an island with a number of cities connected by two-way roads. Road network is designed in such a way, that there is exactly one possibility to drive between any pair of cities (without turning back).
Unfortunately, hard times have come - Byteland is preparing for a war. The Lead Strategiest of Byteland is preparing a plan of defence of Byteland, which takes into account creation of a special security zone. The zone will be created by blocking some of the existing roads in Byteland in such a way, that it won't be possible to drive through these roads. In order to make the zone completely secure, following rules have to be fulfilled:
Many different solutions to the problem are being considered - for different values of k, it is required to determine how many roads have to be blocked at minimum, to obtain a special security zone of size k (consisting of exactly k cities). Help the Lead Strategiest of Byteland - write a program which for specified value of k calculates required number of barricades.
Write a program which:
The first line of the standard input contains one integer n (1 ≤ n ≤ 3 000), representing the number of cities in Byteland. Cities are numbered with numbers 1, 2, ..., n.
Each of the following n - 1 lines of the standard input contains pair of integers a, b (1 ≤ a, b ≤ n) separated with single space. Pair a, b represents a direct road connecting cities a and b. Each pair of cities is connected with at most one direct road.
In the following line of the standard input there is an integer m (1 ≤ m ≤ n) - it is the number of queries to process. Each of the following m lines contains one integer ki (ki ∈ {1, 2, 3, ..., n}). It represents query number i - the number of cities that have to be inside i'th special security zone.
Your program should write to the standard output exactly m numbers, each of them in a separate line. The number in i'th line should be:
7 1 2 1 3 2 4 2 5 3 6 3 7 2 2 3
2 1
Contest > Algorithmic Engagements > PA 2007 7-1번