|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||256 MB||12||6||6||50.000%|
There are N islands where beavers live. The islands are numbered from 1 through N. These islands are connected by N − 1 bidirectional bridges. The bridges are numbered from 1 through N − 1. The bridge i connects the island Ai and the island Bi. It is possible to travel between any islands using some bridges. Each island is inhabited by a beaver.
Sometimes, beavers living in some islands gather in an island, and have a meeting. When the attendees of a meeting are fixed, one of the islands satisfying the following condition is chosen as the location of the meeting:
The sum of the numbers of bridges the attendees have to pass through to gather in the chosen island is minimized.
Here, when the attendees of a meeting are fixed, each attendee of the meeting moves from his/her island of residence to the location of the meeting by passing through the minimum number of bridges.
The attendees of a meeting are looking forward to it very much if there are many candidates for the location of the meeting. When the attendees of a meeting are fixed, the expectation score of the meeting is calculated as the number of candidate islands for the location of the meeting satisfying the above condition. For each integer j between 1 and N, inclusive, you want to know the maximum expectation score of a meeting where j beavers will attend.
Write a program which, given the information of the islands, calculates, for each number of attendees, the maximum expectation score of a meeting.
Read the following data from the standard input. Given values are all integers.
N A1 B1 . . . AN−1 BN−1
Write N lines to the standard output. In the j-th line (1 ≤ j ≤ N), output the maximum expectation score of a meeting with j attendees.
N ≤ 16.
N ≤ 4 000.
No additional constraints.
5 1 2 2 3 4 2 3 5
1 4 1 2 1
For example, we consider a meeting where the beaver in the island 1 and the beaver in the island 3 will attend. For each island, the sum of the numbers of bridges they have to pass through is calculated as follows.
The candidates for the location of the meeting are the islands 1, 2, 3. Therefore, the expectation score of this meeting is 3.
7 1 2 2 3 3 4 4 5 2 6 3 7
1 5 1 3 1 2 1