这玩意儿跟启发式合并一样 都有一种的暴力的美感QAQ

今天一天就写了三道题我还是滚去月考吧（瘫xxx

本来今天是一定要学完动态点分啊结果神游了好久w（<-这玩意真的不怎么好懂啊

dsu：

https://blog.csdn.net/QAQ__QAQ/article/details/53455462

https://www.cnblogs.com/zzqsblog/p/6146916.html

长链剖分：

https://www.cnblogs.com/zzqsblog/p/6700133.html

https://www.cnblogs.com/galaxies/p/cogs2652.html

https://zhuanlan.zhihu.com/p/25984772 （每次打开看到picks学长就只能无尽膜拜orz

感觉今天学的东西……嗯奇奇怪怪吧 适用性不是特别广

但是如果能转化模型的话我想会比暴力数据结构或者其他高级算法要好写好弄很多

我们可以知道 树上轻重链剖分所能达到的效果是惊人的

由于每次/2的原因 所以对于轻链常常可以乱搞

那么我们的主要想法就是减少处理重链的次数 无论是树链剖分/dsu/长链剖分都是秉承着这样的想法

链剖-> 将重链dfs序化为连续区间 方便线段树操作/找lca

dsu-> 先处理轻子树 暴力消去 再处理重子树 保留结果 再暴力加上轻子树 得到此处答案（最值与求和都可做 不过只限于与子树有关的问题 且不支持修改）（相当于是树上莫队的一种新做法？）

长链-> k级祖先问题可得到性质（其k级祖先所在链长一定大于k） 那么在链头记录二进制下各位父亲与上下链长的的节点信息 就可以在查询时先解决最高位的2之后(此时k减半了)，然后剩下的k一定是在跳上去位置的已记录的链长范围中的（说白了就是平衡关系而已 在不会过的情况下记录适当信息）用这个方法做的好处是预处理O(nlogn)，而查询是O(1)的。

还有就是一种看上去是点分板子的东西 然而在那道题还需二分的情况下 如果出题人愿意是可以卡掉点分O(nlogn)的，但是长链剖分这个东西反而是O(n)的。

首先是把上面判定prefer的标准换成子树中最深深度 

然后我们不管轻的 只做重的，然后再统一过掉轻的，组合，更新。 

这个适用于涉及深度的的树上问题。

这些内容其实都是一个log思想

这个思想真的很妙 就是一种莫名暴力美 真的超级厉害啊！

希望能多多将这样省代码的利器进行模型的推广！