[POI 13 Stage 2]101 - 捷運路線 (Subway)

Sylveon

原題：http://hoj.twbbs.org/judge/problem/view/101
AC：http://hoj.twbbs.org/judge/judge/submission/33133

我們先找出直徑上最遠的點R，將R為根作樹鍊剖分，不果剖的是最深的鏈，並將鏈縮成點權為鏈上點數的點。把前[tex]min(C,1+(L-1)*2)[/tex]大的點權加起來就是答案，C是切出的總鏈數。
可以用數學歸納法證明其正確性：
如果L=1，那樹鏈剖分的最長鏈會是樹的直徑長。考慮由P條鏈擴張成P+1條鏈的方法：
新增的一條鏈一定是原有答案鏈的分支，如果P+1鏈的答案不與原有答案相交/臨，考慮該鏈與原有鏈的連線Z，會發現如下圖方法修改，可使答案增加，所以原來方法並非最佳答案。

第二步要證明的是對新建的圖擴張兩次，可使用P鏈的方法擴張為用P+1鏈的方法。有兩種情況：新點-舊點-新點、舊點-新點-新點：擴張的路線圖如下(待補)


第三步：P鏈到P+1鏈擴張最多只能有兩次。
第四步：點權重必由點權最大的的點向外(child)嚴格遞減，所以我們每次擴張時，選擇向外延伸的點權最大的點任意一個都是最佳解，所以我們只要貪心選擇權值最大的就是最佳解，並能推到P+1的最佳解。實現大概如下附的Code
[sojcodepad]2845acba[/sojcodepad]