熟悉了云和闪电的脾气，就不再迷惑。
主体介绍
边分树是个针对边分治的扩展算法，和点分治到点分树类似的，我们试图把边变成点并连接起来得到一颗新的树。此时这棵树可以描述一个点在边分治过程中的所属连通块。
具体操作
我们把边变成点，根据边分治的过程，连接起来得到一颗新的二叉树。可以拟定一条边节点大的那一个联通块中的切割边节点在左子树，当然，拟定在右子树也是可以的。
由于一个边可以原来的连通块划分两个连通块，因此在一次划分之后，原来连通块中的点将被分配到链两边的联通块的其中之一（如图一）。
这个时候继续寻找要切开的边，就变成了在两个连通块中独立寻找，也仅和所属连通块中的点有关系。因此，我们可以根据一个点在每次边被切割后的所属连通块来为这一个点构造一个整体边分树的从根到叶子的链。
举个例子，比如对于一个点，假设它在第一次切割中被分配到了整体边分树中左子树边所在的连通块，那么此时在这个点的边分树链里，我们就把右边子树给舍弃了，这是类似动态开点线段树的（如图二）。
不难发现，实际上这条链描述了这个点在每次切割后的归属。利用这一点，我们就可以得到一个结论：对于两个原树上的节点，他们边分树链中深度最深的边将这两个点切成了不同的连通块中的点。
对于每个点，我们可以储存它们在边分树过程中到各个连通块根的信息和。而边分树链上的一个点，正好描述了一个切割后两个连通块各有各的根的样子。因此我们可以将这个边分树上的每个点储存该节点在这个状态的时候，到达根的信息和。由于边分治的性质，这些信息总量是 \(O(n\log n)\) 的，而且我们可以直接暴力在每次切割后计算，不会消耗额外的时间，也就是说，这需要花费 \(O(n\log n)\) 的时间，而空间同样也是 \(O(n\log n)\) 的。
这个时候，我们就把边分治的过程给描述了，所以我们就可以支持一些更加不顺序的询问，在这一点上，它和点分树可能是类似的。
比如，我们可以使用这个数据结构在线地 \(O(\log n)\) 每次地回答两个点之间的距离。这是原来的边分治所做不到的，他需要离线。
例题
[CTSC2018] 暴力写挂
有对答案式子的变换：
因此考虑边分治，在一次分割中，如果我们将到当前连通块的根的距离加上原树深度作为 \(val(x)\)，那么此时答案就是 \(val(x)+val(y)+w(e)-2\text{depth}'_{\text{LCA}'(x,y)}\)，其中 \(x,y\) 在两个不同的连通块里面。
此时计算 \(2\text{depth}'_{\text{LCA}'(x,y)}\) 变成了难点，一个做法是对于 \(T_2\) 建出虚树，直接枚举 \(\text{LCA}'(x,y)\)，然而这是 \(O(n\log^2 n)\) 的，难以通过。
我们考察建虚树的目的实际上是不能够直接枚举 \(T_2\) 的 \(\text{LCA}'\)，因为点分治是离线的，因为它给出的数据是离线获取的，因此我们不可以在线地在边分治中询问用来迎合枚举 \(\text{LCA}'\) 所需要的在线。
因此考虑描述了边分治过程的边分树，它可以支持在线的询问。
因此我们可以做这样一件事情，在单点的边分树链的节点维护 \(val\) 信息。然后在 \(T_2\) 上枚举 \(\text{LCA}'\)，此时对于一个枚举的点，\(x,y\) 分别位于不同的子树中，因此我们需要维护每颗子树的边分树（在一开始，叶子的边分树就是它的边分树链）。这个时候我们同时做合并和对答案贡献的过程，具体来说是，我们维护前 \(k\) 个子树的边分树，此时考虑 \(k+1\) 颗子树的边分树，我们对于每个两个边分树都有的节点，对于答案更新 \(val(lson_u)+w(e)+val(rson_v)-2\text{depth}'_{rt}\)，\(val(rson_u)+w(e)+val(lson_v)-2\text{depth}'_{rt}\)（如果没有左或者右节点就不管）然后，在合并后的树上将该节点的 \(val\) 设置为 \(\max(val(u),val(v))\)。
最后别忘了考虑单点的情况，它并没有被点分治或者说是点分树考虑到，以及答案需要除以二。