【UOJ#33】【UR #2】樹上GCD

求解樹上兩個點到lca的距離的最大公約數是k的對數

首先我們很容易就想到莫比烏斯反演，那么利用倍數形式，我們只需要求解是i的倍數的對數。

考慮枚舉lca，這個問題就和深度有關，那么可以長鏈剖分，然后每次枚舉倍數是O(dlogd)的，但是這里的深度不止是輕鏈還有重鏈，那么復雜度就不對了。

但是我們發現當這個倍數很大時復雜度是正確的，每次維護輕鏈的倍數，然后對于每個倍數跳，總復雜度就是$O(n\sqrt{n})$。但是很小的時候就不對了，但是我們利用根號分類討論，發現很小的數最多只有$O(\sqrt{n})$個，那么我們可以直接存下來這些數，用一個數組g[i][j]表示深度模i為j的點有多少個。

這樣子大的數我們直接暴力，小的數進行存儲，就可以實現復雜度平衡。

總結

以上是生活随笔為你收集整理的【UOJ#33】【UR #2】树上GCD（长链剖分/根号分类讨论）的全部內容，希望文章能夠幫你解決所遇到的問題。

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