Problem : 79 - 滅人器

Problem Statistics

Solved Member: 10　　Submission: 124　　User Tried: 10

Statement:

自從兔王征服的銀河系，他決定蓋一個超大的皇宮！
皇宮有n個房間，有n-1條路來連接，使得每兩個房間有一條路連接。

根據消防法規定，他的房間必須滿足下面的要求。

1.滅人器必須放在房間裡，一個房間可以放任意多個滅人器。
2.每個房間必須要指定一個滅人器，而且房間之間可以共用同一個滅人器。
3.一個滅人器最多只可以被s個房間指定。
4.一個房間與他指定的滅人器距離不超過k。

兔王希望建造成本越小越好，又希望他的皇宮至少能滿足消防法的規定。
他想請你幫他計算最少需要買幾台滅人器。

Task:

請你根據消防法的規定，計算皇宮至少需要買幾台滅人器。

Input:Output:

第1行有3個整數，n,s以及k，用空格區隔開來，其中1 ≤ n ≤ 100000，1 ≤ s ≤ n，1 ≤ k ≤ 20。
接下來下面有 n-1 行，每行有2個數字Xi Yi，代表Xi以及Yi有通道連接。且滿足1 ≤ Xi , Yi ≤ n。

輸出只有1個數字，代表至少需要幾台滅人器。

Sample Input:Sample Output:

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

HINT:

上面為最佳方案其中一種配置方法，在8擺兩罐，9與12各擺一罐。

Source:

POI 16 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	2000ms	65536kb
1-ocen	2000ms	65536kb
1-1	4000ms	65536kb	10
1-2	4000ms	65536kb
2-ocen	2000ms	65536kb
2-1	4000ms	65536kb	10
2-2	4000ms	65536kb
3-ocen	2000ms	65536kb
3-1	4000ms	65536kb	10
3-2	4000ms	65536kb
4-ocen	10000ms	65536kb
4-1	4000ms	65536kb	10
4-2	4000ms	65536kb
5-1	4000ms	65536kb	10
5-2	4000ms	65536kb
6-1	4000ms	65536kb	10
6-2	4000ms	65536kb
7-1	4000ms	65536kb	10
7-2	4000ms	65536kb
8-1	4000ms	65536kb	10
8-2	4000ms	65536kb
9-1	8000ms	65536kb	10
9-2	8000ms	65536kb
10-1	8000ms	65536kb	10
10-2	8000ms	65536kb
10-3	8000ms	65536kb