bzoj3052糖果公园 树上莫队

题目传送门: 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：