三倍经验：
加强版：
-
先看 bzoj #3522 这题。容易想到时间 \(O(n^2)\) ，空间 \(O(n^2)\) 的树形 dp 。设 \(dp_{1/2/3, u, i}\) 表示以 \(u\) 为根的子树中所有以 \(u\) 为一端点，长度为 \(i\) 的路径中选 \(1/2/3\) 条路径的方案数（注意，这个方案数选的几个节点的 LCA 必须都是 \(u\) 节点
-
转移显然，跑个换根即可
-
但这个代码放到 P3565 上会 MLE ，考虑优化空间复杂度
-
设 \(f_i\) 表示以当前节点为根时深度为 \(i\) 的点的个数， \(g_i\) 表示以当前节点为根时选两个深度为 \(i\) 且 LCA 是根的方案数， \(pre_i\) 表示当前考虑的这些儿子中深度为 \(i\) 的路径个数
-
容易得到转移：
\[ans \leftarrow ans + g_i \times f_i \\
g_i \leftarrow g_i + pre_i \times f_i \\
pre_i \leftarrow pre_i + f_i \\
\]
- 最终复杂度 \(O(n^2)\) ，但空间优化到了 \(O(n)\)
- 最后考虑加强版，要用长链剖分所以鸽了