Problem : 101 - 捷運路線

Problem Statistics

Solved Member: 17　　Submission: 87　　User Tried: 18

Statement:

兔子國最近在 N 個站之間建立好了捷運的軌道，這些站分別由 1 標號到 N 。
為了節省成本，兔王只用了 N-1 條雙向的軌道連接這 N 個站，使得任意兩站之間恰有一條唯一的路線可以通行。

兔王現在想要把這些路分成 L 條直線的路線，這些路徑必須遵照以下的規則：
1.從一站開始，到一站結束的路徑，長度不限
2.任意兩條路線可以交叉，重疊，共用同一個站
分配的方法就跟台北捷運的路線很像(藍線、綠線、紅線.......)

兔王現在想要了解，在建 L 條路線的情況下，最多能有幾個站「至少被一條路線覆蓋」?

Input:Output:

輸入第 1 行有兩個正整數 N,L(2 ≤ N ≤ 1000000; 0 ≤ L ≤ N)，代表站的數量以及兔王想建造的路線數。
後面的 N-1 行每行有兩個整數 A,B，代表 A,B 兩站直接連通。

輸出只有 1 行，請輸出最多能有幾個站被路線覆蓋。

Sample Input:Sample Output:

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

HINT:

如圖，細線為原本的鐵路，每條粗線為 1 條線路。
圖上為最佳解的其中一種分配方法，共有 13 個站被覆蓋。

Source:

POI 13 Stage 2

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	131072kb
1-ocen	1000ms	131072kb
1-1	1000ms	131072kb	9
1-2	1000ms	131072kb
1-3	1000ms	131072kb
1-4	1000ms	131072kb
2-ocen	1000ms	131072kb
2-1	1000ms	131072kb	9
2-2	1000ms	131072kb
2-3	1000ms	131072kb
3-ocen	1000ms	131072kb
3	1000ms	131072kb	9
4-ocen	1000ms	131072kb
4-1	1000ms	131072kb	9
4-2	1000ms	131072kb
5-ocen	5000ms	131072kb
5-1	1000ms	131072kb	9
5-2	1000ms	131072kb
6-1	1000ms	131072kb	9
6-2	1000ms	131072kb
7	3000ms	131072kb	9
8-1	3000ms	131072kb	9
8-2	9000ms	131072kb
9	9000ms	131072kb	9
10	9000ms	131072kb	9
11-1	20000ms	131072kb	10
11-2	9000ms	131072kb