題目傳送門: http://www.lydsy.com/JudgeOnline/PRoblem.php?id=3052

最近不太想寫博客了，退役前還是寫點學的東西吧。 這個坑從我會莫隊開始就挖在這里了。。 莫隊： http://blog.csdn.net/nickwzk/article/details/52954097 可是在樹上怎么莫隊呢？ 這有兩種非常妙的方法，dfs序和王室聯邦分塊（bzoj1086） 我看網上大家都用dfs序的版本，就作死寫了一個王室聯邦分塊的，然后常數巨大（大概不怪王室聯邦分塊怪我常數大 然后這個是一個樹上的帶修改的莫隊，所以當塊大小等于n23$n^{/frac{2}{3}}$的時候復雜度最優。 借用王室聯邦分塊，另塊大小為B=n23$n^{/frac{2}{3}}$，塊的個數為p。每個節點i屬于belong[i]。我們可以發現（belong[u], belong[v]）最多p2$p^2$個取值。 因為已經按塊排好序了，所以我們可以將情況分為兩種。一種是當前移動后u,v都在原塊內，那么移動總復雜度為O（B?q$B*q$）；另一種是u,v不在原來的塊內，那么這種情況最多出現p2次$p^2次$，每次移動最壞情況為O（n+n+q$n+n+q$）。又因為n與q同階，所以可以得到總的時間復雜度為O（n53$n^{/frac{5}{3}}$） 然后在樹上移動的時候，記錄一個vis數組，到達一個點的時候將其取反，如果已經存在當前統計中就將它刪去，若沒有就將它加入。對于時間的修改可以放在移動之前也可以放在移動之后，必須要使這個操作可逆，所以修改之后要記錄下修改之前的糖果種類。 對于lca（u,v），要在記錄答案之前加上，在記錄答案之后刪去。 自帶巨大常數的Code：