这是一道很不错的理解长剖优化 DP 的题。u1s1 长剖比重剖以及 dsu on tree 需要脑子多了（
我们注意到，符合条件的 ((x,y,z)) 只可能是一种模型：
b
/
a z
/
x y
其中 (a=mathrm{LCA}(x,y),b=mathrm{LCA}(x,y,z))。显然需要满足 (dis(a,x)=dis(a,y)=dis(a,b)+dis(b,z))。
因为 (b) 能让所有节点包含在子树内，所以考虑枚举 (b) 来贡献。然后就是关键一招（强国之路）了（其实这一步是可以在多次尝试屡次失败后最终试到的（）），我们考虑让 (dis(b,z)) 来作为贡献者，这样 (b) 的左右两边就相对独立了，只需要搞出对于每个 (dis(b,z)) 左右两边的方案数，其中左边是只要满足两种距离的差值等于 (dis(b,z))，有效的减少了需要维护的信息。
我们考虑 (f_{i,j}) 表示子树 (i) 内相对深度为 (j) 的点数，(g_{i,j}) 表示子树 (i) 内满足 (dis(a,x)=dis(a,y)=dis(a,i)+j) 的无序对 ((x,y)) 的数量。用这两者显然就可以轻松的表示出答案式了，并且这两个东西后续可以 DP 转移。它们是对每个点都有该子树深度个值的，不过不用慌，这种大概率能用长剖优化，反而应该高兴。
对答案的贡献的话，由于要求 (a,z) 不在同一儿子子树内，所以需要枚举儿子（这也恰好符合长剖的特征，由儿子贡献上来）。那么注意到 (a=b) 和 (b=z) 这两种特殊情况，无法往下挖一步儿子，需要简单的特殊处理一下。(a=b) 就由 (f) 按儿子序列扫一遍，维护当前从 (1,2,3) 个儿子子树中每个选一个深度为 (j) 的点的方案数；(b=z) 就是 (g_{i,0})。
那么对答案的正常贡献，我们考虑枚举 (dis(b,z)) 和 (a,z) 两者分别所在儿子子树：
显然可以用 (f) 的整体和优化掉一维。那么这一部分的复杂度，可以看成每个节点都对复杂度有子树深度的贡献。贡献方式有两个，一是参与整体和的计算，而是被枚举到对答案进行贡献。要想长剖优化的话，唯一的思考点在于如何常数继承深儿子，或者说把对深儿子的继承工作给与浅儿子的复杂度均摊掉，这一点只需要它不关于深儿子子树深度大概率就可以做到。对于贡献方式的前者，我们设最大浅儿子子树深度为 (mx)，将深儿子继承上来的 (f) 的前 (mx) 个给直接算进去即可，这样复杂度显然是得以均摊的；对于后者也一样，只搞前 (mx) 个，后面的都无效（因为另一个因数一定为 (0)）。
下面考虑 (f,g) 的转移（求法）。(f) 很简单，有
这就是最常规的长剖了吧。考虑如何常数继承深儿子，就将 (f) 右移一位，并在第一位添上 (1) 即可。这个东西可以用 deque 来维护（仿佛社会上大多数人用指针维护，我不喜欢这样，看起来没有 deque 自然，不过要是被卡常了就没办法了）。
然后是 (g)，它想往儿子转移的话，需要满足 (dis(a,b)geq 1)，否则即 (a=b) 的话需要枚举 (x,y) 所在儿子子树用 (f) 转移，有
前面的和式是个左移。后面显然可以前缀和优化，考虑如何搞。就维护一个实时的关于各深度的前缀和，实时更新即可（不能开数组预处理前缀和，因为那样复杂度就变成了轻儿子数乘以最大轻儿子子树深度，就假掉了）；对于深儿子的常数继承，跟整体和类似。
这样就长剖做完了。代码有点长，但是每一步都非常机械化，并不容易写错。来列举一下这种复杂长剖的需要注意的点吧：
- 继承深儿子时，该贡献的先贡献掉，然后再修改，尤其是该节点上的信息的贡献一定要推后。
- 可能需要开一堆临时空间（
vector之类），需要搞一个防越界函数，取值就判下标合法，引用就while(不够)push_back;。 - 千万不要把临时空间放到全局，这样如果每 dfs 完一个轻儿子就改一次，会在 dfs 轻儿子的时候被改掉或者被清空。