有人说，直接点分树，力大砖飞，非常不错！
实际上这种做法非常的垃圾，很多时候我们使用点分树，一定是不得不使用点分树，比如模板题，强制在线，非常的恶心，所以我们使用点分树。
而点分树是否必要呢？既然你能看到这篇blog，他肯定是不必要的！我们今天来发掘dsu on tree的美妙性质，让他求解这个问题！
然后就是我们考虑dsu on tree如果传统从子树向上合并，非常劣，因为这样的结构既我不会可持久化，而且不能够处理子树外信息，非常垃圾。
所以我们考虑自顶向下拆分轻儿子，这个结构非常有趣，首先时间复杂度证明沿用dsu on tree的时间复杂度证明，同时支持可持久化，这个我们先放到一边，最主要的是，他可以维护邻域了。
邻域一直是一个很神秘的东西，看着就跟dsu on tree无缘，但是我们通过这样的方式，他的结构就变得能够维护邻域了，非常的让人开心。
但是如何维护呢？如果每个点都分裂肯定会爆炸，怎么办呢？
考虑我们优先走重链，那么轻儿子因为是挂上去的，所以可以直接合并，我们有距离公式 \(dis(a,b)=dep_a+dep_b-2dep_{lca(a,b)}\)，因为这个轻儿子是挂到重链上的，所以 lca 我是确定的，换句话说，我们可以把 \(dep_a-2dep_{lca(a,b)}\) 存到一个数据结构或者干脆就是一个桶里面去，然后用 \(dep_b\) 来查，这部分因为用的是同一个坐标所以合并到同一个数据结构里面去。
然后走轻边的时候，把当前子树信息从主子树信息中删除，然后开一个新的数据结构，旧的保存就好，顺便储存一下旧的版本的 lca（因为不能直接储存dep-2lcadep，直接储存的话时间复杂度是错的），每次需要查询邻域的时候调出来查询就好了，因为到根链轻边只有log条，所以时间复杂度是对的，到这里我们成功 \(\log^2\) 解决了这个问题。
首先大家知道dsu on tree 没办法在线，实际上真的没有办法吗？传统做法我不会，但是这个做法非常容易的我们就能够做到可持久化，一下子就支持在线了，非常的叫人喜欢！！！
相较于点分树，这个算法常数非常小，而且大多数时候跑不满，根据个人需要可以选择线段树或者树状数组维护。
而且最重要的，这个巨好写好调，模板我整理一下就发出来。
标签：一个点,dep,tree,复杂度,dsu,邻域,求法,lca From： https://www.cnblogs.com/kisara-no-inu/p/18173842