LTIME21

domen111

Heavy-light Decompositions AC code:
http://www.codechef.com/viewsolution/6361466
英文的官方詳解: http://discuss.codechef.com/questions/64883/hldots-editorial


題意:
求有幾種樹練剖分方法數，一個合法的樹練剖分定義為從根節點到任意節點所經過的輕邊不得超過log2(N)，N為節點總數。


比賽時本來以為這題是應該照樹練剖分的方法去做，後來發覺就算不是依照樹練剖分的方法(重邊連到重兒子)也可能符合題目要求(log2)的性質。

這題其實DP一下就行了
dp[i ][j], i:節點編號, j:連到此節點前的輕邊數量, dp[i ][j]=方法數
轉移時枚舉連接子節點的邊作為重邊，乘一乘計算方法數在加起來就行了
計算連乘的時候不要太暴力直接乘，否則複雜度變成O(C[sup]2[/sup])(C為子節點數)就只能解出小測資，記得先預處理一下，轉移複雜度為O(C)、總複雜度為O(NlgN)就能完全AC。