小技巧—邊權轉點權

小技巧—邊權轉點權

很多算法，比如樹鍊剖分，是在點權上進行計算和統計的。

詳解樹鍊剖分

但是有些題會比較狗，隻給你邊權。

這時就要想辦法把邊權轉為點權。

以一棵樹為例。邊權轉點權一般是把邊權轉為深度較深的節點（也就是兒子節點）的點權。

這麼做很好了解，因為對于一棵樹來講，一個點有很多個兒子（出邊），是以沒辦法把這些出邊的邊權都集中在一個點上，但是一個點隻有一條入邊。是以我們選擇這種政策。

需要注意的是，在邊轉點之後，如樹鍊剖分之類的統計會出現變化。

顯而易見，邊轉點之後，每個點代表這個點本身和它的入邊這條路徑，是以在我們統計一條線段路徑的時候（從一個點開始，到一個點結尾），就不能同時包括其兩個端點（理由已經給出）。否則就會錯。

幸甚至哉，歌以詠志。