T4 树上计数

对于 $n\le 5000$

可以通过 $n^2$ DP 解决。

$f[i][dis]$ 表示 $i$ 子树内距离为 $dis$ 的点数。

$g[i][dis]$ 表示 $i$ 子树内选取两点，满足两点到其 LCA 的距离为 $d$，LCA 到点 $x$ 的距离为 $d − i$ 的方案数。

为什么这么设计呢，你要考虑三个满足条件的点，他们三者的 LCA 并不一定是产生贡献的中间点，于是我们把贡献点设计在 $g$ 中两点的 LCA 上面。

$i$ ( $f$ 方案中的点到 $x$ ) $+ d-i$( $x$ 到 $g$ 方案中的两点 LCA ) $= d$

于是就可以直接树上 DP 了。

对于 $x$ 每个儿子 $y$，有:

$g[x][i]+=f[x][i]*f[y][i-1]+g[y][i+1]$

$f[x][i]+=f[y][i-1]$

然后答案的话只需要：

$ans=\sum_{x=1}^n \sum_{y\in son(x)}\sum_i f[y][i-1]*g[x][i]+f[x][i]*g[y][i+1]$

考虑每个点在其父亲上统计一次贡献，所以复杂度是 $O(n^2)$。

对于数据随机，树高是 log 级别的，可以暴力处理出离一个点 $x$ 距离为 $d$ 的点数 $s$，然后 $C_{S}^3$ 加起来就好了。这个三十分还是比较好拿的。

接下来对于 $n\le 10^5$，考虑去优化前面的 $n^2$ DP。注意到一个点可以直接从它其中一个儿子快速继承过来，只需要 $f$ 右移一位， $g$ 左移一位。

那么可以长链剖分，继承长儿子的 $f$ 和 $g$ 再按照上述过程暴力合并剩下的，能保证复杂度为树中所有长链的长度之和。

于是复杂度变成了 $O(n)$。