P3345 [ZJOI2015]幻想鄉戰略游戲

帶修改帶權重心
這是經典的樹上尋找關鍵點的題目，我們使用點分治處理這個問題，因為點分治的特性，就相當于在樹上二分了。但是這與倍增不同，倍增只是在鏈上二分，而點分治則是在整棵樹上二分。

然后我們考慮如何二分，顯然帶權重心的位置和邊權無關，并且每次只需要尋找一個點的$2su{m}_v>su{m}_u$那么重心一定在這個子樹內部。也就是說有一個兒子的答案比當前點小，那么重心就在這個子樹內。我們可以維護3個變量。
$sumd$:表示當前分治范圍內$d_u$的總和
$sdv:$表示當前分治范圍內$d_{u}dis(u,v)$的總和
$sdvf$：表示當前分治范圍內$d_{u}dis(u,f{a}_v)$的總和

然后我們通過跳祖先節點容斥就可以計算出當前點作為重心的答案，復雜度是$O(logn)$所以查詢我們可以從根開始，然后每次遍歷所有兒子，查詢對應的答案，找到答案最小的，進入它所對應的子樹，然后繼續這個過程，知道所有兒子的答案都大于等于當前點答案那么就找到了重心。

然后我們考慮如何修改，只會影響到當前點的所有祖先節點，所以我們暴力跳祖先進行修改即可。然后這道題最好使用st表處理lca。

細節錯誤：

一定要注意循環終止條件是f[i]!=0，相當于我們每次都是處理f[i]的有關信息

處理的時候距離計算是dis(x,f[i])而不是dis(i,f[i])

總結

以上是生活随笔為你收集整理的P3345 [ZJOI2015]幻想乡战略游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。