Alas!!! 都好久没写过算法总结了。
0. 引子
模板：给定一棵树，求对于给定的 \(k\) 使 \(dist(i, j) = k\) 的 \((i, j)\) 的个数。\(1\le n\le 2\cdot 10^5\)
这题的朴素做法：枚举 \(i\), \(j\) 进行累计答案，时间复杂度为 \(O(n^2\log n)\) 。显然过不了。
然后想到了树形DP，设 \(f_{i,j}\) 表示 \(i\) 的子树中到 \(i\) 的距离为 \(j\) 的节点个数。
但是这样的话需要枚举任意两颗子树，然后相乘，复杂度依然爆炸。
1. 淀粉质思想
分治，就是把大的问题分成小的问题递归解决，再合并答案。
上面的树形DP的劣势在于：\(f_{i,j}\) 会出现大量的 \(0\)，统计这个简直就是浪费时间，直接对于每个节点用 \(k\) 减去 \(i\) 到根节点的距离然后统计有多少节点离根节点的距离为这个数不就好了吗。
那这样的话还需要一个桶：\(b_i\) 表示已经遍历过的节点中到根结点距离为 \(i\) 的节点数量。每颗子树都是先统计答案，再把一个个节点加入桶里。
然后就发现 \(f\) 数组就不是很必要了。对于 \(i, j\) 在同一个子树的答案，我们把这颗子树拎出来然后在进行一遍上述操作就ok了。
总结：把满足要求 \(i, j\) 分为两类：
- \(i, j\) 在不同的两颗子树：这种情况用桶统计即可。
- \(i, j\) 在相同子树：对这棵子树分治处理。
然后就ok了。