1239 . 致命武器 Lethal Weapon
TopCoder
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
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 |