TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

34.9% (15/43)

Tags

Description

最近一種新型的致命武器風靡黑道社會,那就是:"n減一節棍"!!
也不知道誰,把雙節棍改裝成n-1節棍棍子所構成的兵器,想不到效果奇佳,堪稱居家旅行殺人滅口的必備兵器
最有趣的是,這個優美的兵器很巧就是個n個節點(n-1條邊的)的tree!!
這真是太神奇了,卡恩!

不過這個武器之所以稱為致命武器,是因為它有一個致命缺點:
那就是由於它實在是太多節了,又加上他是tree形而非chain形的,以至於難以收藏,
你的任務就是要幫忙黑幫老大把這"n減一節棍"分成若干節,以利收藏

但非常巧的(也非常不幸的),黑幫老大也是個演算法狂熱份子,
他決定讓你的日子更難過些,為了節省功夫,他希望他的"n減一節棍"被該拆成最少節
其中每一節都是一個chain(沒有分支的長鍊),而且每一個chain都要一樣長(由一樣多節所構成)

請你幫幫忙
給定"n減一節棍"(一個n個點的tree)的長相,請輸出每段是多長

Input Format

每次輸入只有一組測試資料

第一行有一個整數n,代表總共節點數 (節點編號由0~n-1)
接下來n-1行,每行有兩個0~n-1的整數,代表該兩個節點有邊相連

輸入給定的圖會是一個tree。
2 <= 節點數n <= 10,000

Output Format

請輸出一個整數,代表分成最少段時,每段是多長。

Sample Input 1

16
0 1
1 2
0 6
0 3
3 4
4 5
0 7
7 8
8 9
9 10
0 11
11 12
12 13
13 14
14 15

Sample Output 1

5

Hints

可拆成以下3段:
2-1-0-3-4-5
6-0-7-8-9-10
0-11-12-13-14-15

每段長度為5

Problem Source

原TIOJ1239 / TIOJ例行賽IV, Problem Setter: kelvin

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 5
19 18 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7
7 2000 65536 262144 8
8 2000 65536 262144 9
9 2000 65536 262144 10
10 2000 65536 262144 11
11 2000 65536 262144 12
12 2000 65536 262144 13
13 2000 65536 262144 14
14 2000 65536 262144 15
15 2000 65536 262144 16
16 2000 65536 262144 17
17 2000 65536 262144 18
18 2000 65536 262144 19