聊聊 dsu on tree |

契约签订完毕，接下来要认真起来了。

简介

对于子树查询类问题，大多可以 dfs 序然后上数据结构，不行就树上莫队。

一个方法是 dsu on tree，是一个好写的复杂度 $O(n \log n)$ 离线算法。

考虑启发式，对于每个节点找出重子树，然后

对于复杂度，总操作次数为 $n+\sum$ 轻子树大小。类似于树链剖分，每个点被多操作一次就代表成为了一次轻子树，而轻子树的父亲的子树大小至少为轻子树的 $2$ 倍，所以每个点至多被操作 $\log$ 次。

加入重儿子之前的全局所有贡献都是被删掉了的。

这意味着 dsu on tree 和 $O(n^2)$ 去统计在贡献处理上没有任何区别，也意味着回滚莫队能做的都能做。

直接 dsu on tree，求众数和可以正常做，撤销的时候不仅要把计数的数组撤销，还要把最多出现次数和众数和撤销，后者也好办，操作前记录一个撤销的时候直接赋值就好了。

排序后能是回文串要么每个字符都是偶数，或者只有一个为奇数。

字符只有 $22$ 个，可以记录某些字符出现奇数的最长长度，然后类似于点分治去统计。

把这个过程按照 dsu on tree 做就好了。

如果只询问一个子树，那么就是 dsu on tree 板子。

考虑把 dsu on tree 序列化，先加入轻子树，再加入重子树，再加入根。

当扫描这个序列的所有子树时，轻子树的移动后会直接被删掉，重子树移动后再查询根，重子树会被保留同时加入所有轻子树，扫描的复杂度为 $O(n \log n)$ 。

直接在这个序列上莫队，区间的左右端点为询问的两颗子树。

子树询问的区间移动就如果目标区间当前区间无交就当前区间删除然后暴力加入目标区间，否则就就正常移动左右端点。