边分治用来解决一些点分治中一些解决不了的问题。

比如说点分治时有很多棵子树，合并这些信息时不能保证时间复杂度。

而边分治时最多只会有两棵子树，就可以很好地解决问题。

看到了[Noi2014]购票这道题目，发现了这种操作（为什么之前没想到呢。。。）

代码还没写过，先口胡一下

有根树上的DP，每个点只能从祖先转移。

Prufer序

一个Prufer数列和一个带编号的无根树是一一对应的

树->Prufer序

每次找这棵树中编号最小的叶子节点，将与这个点相连的点加入Prufer序，去掉这个点以及相连的边。重复这个操作直到剩下两个点。

Prufer序->树

设点集$ V={1,2,…,n} $，每次在$V$中找出最小的未在Prufer序中出现过的数，然后在$V$中删除，与Prufer序中的第一个数相连，Prufer序中的第一个数删除。重复这个操作直到$|V|=2$（Prufer序为空），最后将$V$中的两个点相连。

dsu on tree

可以用来解决一些有下列性质的问题：

1. 对子树询问
2. 没有修改

算法

算法步骤如下：

• 遍历的一个节点
  • 递归所有的轻儿子
  • 递归重儿子
  • 统计轻儿子对答案的影响
  • 计算答案
  • 如果自己是轻儿子，消除影响