淀粉质（点分治）可以用于求树上路径统计之类的问题，扩展有 dfs（点分树）算法

点分治

(相关资料图)

思想：

每次将重心删除，将路径分为经过当前重心与不经过的，然后分成多个联通块，递归下去处理即可。

感觉细节比较多，难写，而且要用一些小技巧（

代码太丑了不想放

习题：

P2634，P3806，P4149，模板

P4178，点分治 + 树状数组

CF914E，点分治 + 状压

CF150E，套路，二分中位数，长链/点分治 + 线段树

点分树

我们将当前联通块重心与上一层重心相连，得到了点分树

性质：

点分树上两点的 LCA 必然在原树两点路径上（画图就看出来了

点分树最大深度为 log n（显然

每个节点子树大小和上限 n log n

思想：

综上，我们得到一个极其暴力的做法：

对于询问节点 x，先统计其子树贡献。

然后向上一直跳到点分树根节点。

假设从 v 跳到 u，每次增加上在 u 子树内而不在 v 子树内节点 w 对 x 的贡献，是 u 子树对 x 贡献减去 v 子树对前者的贡献

并且因为 u=LCA(x,w)，u 在 x 到 w 路径上，所以 x 到 w 贡献能够被拆为 x 到 u 与 u 到 w 贡献

对于修改节点 x，对其每个祖先节点信息进行修改。

对于每个节点 x，开一个长为 x 子树大小的 vector 存信息

相对灵活（

习题：

P6329，P3241，点分树

等暑假再更新吧，咕咕咕

关键词：