시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB135301417.284%

문제

The city you live in just finished construction of its new transport network, PlusRail. There are n stations and exactly one way to get between any given pair of them; this is because there are only n − 1 direct station:station connections. In other words, the network forms a tree.

You have been hired to put together the signage for each of the stations which shows where on the network a passenger is with a big arrow pointing to the bright red station in the centre.

Figure G.1: Illustration of Sample Input 1 and how two designs are reused four times, with the labels painted at different places.

Because the drawings of the network are fairly crude, it is actually possible that you could use the same sign in more than one station, and just write a different permutation of labels for the station names.

If you want to make signage for the whole network, what is the minimum number of unique designs you will need?

입력

  • The first line of input contains the number of stations, n (1 ≤ n ≤ 3 × 105).
  • The following n − 1 lines each contain two distinct vertex indices a and b (1 ≤ a, b ≤ n) indicating that there is a direct route between these stations.

출력

Output the minimum number of map designs that can be made, such that for any station at least one of these map designs can be re-labelled such that this station is in the centre.

예제 입력 1

4
1 2
2 3
3 4

예제 출력 1

2

예제 입력 2

11
1 2
2 3
3 4
4 5
4 6
4 7
5 10
10 9
10 8
7 11

예제 출력 2

10

예제 입력 3

7
7 1
7 2
3 2
7 4
5 4
6 5

예제 출력 3

7

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > The UK & Ireland Programming Contest > UKIEPC 2019 G번

  • 문제를 만든 사람: Robin Lee