考虑以下问题：

给你一棵树，有边权，一条路径合法当它的边权和 \(=k\) ，求合法的路径有多少条。 \((n,k\le 2*10^5,\text{Time Limit=3s})\)

暴力 \(O(n^2)\) ，即对于每一个点dfs它的子树，把边权装桶。

考虑如何优化。

假设树是随机生成的。那么我们的暴力还是没有任何好转 。

但是这是不可能的！

所以，我们本来是选它的子节点继续统计，现在改成选它子树的重心。

于是一切都解决了。

复杂度 \(O(n\log n)\) 。

如果 \(k\le 10^9\) ？

对于每一个点dfs，记录其子树中所有点到它的距离，保存在一个 \(dis[]\) 数组里，然后sort一遍，再用two-pointers或者二分统计答案：有多少 \(dis[i]+dis[j]=k(i<j)\) 。

但是会有 \(i,j\) 在该点的同一棵子树内的情况，此时用容斥把它减掉。

复杂度 \(O(n\log^2 n)\) 。