树上前缀和与树上差分

树上前缀和与树上差分都是树链剖分优秀的离线替代品，配合树状数组还可以进一步处理在线的情况。 ### 树上前缀和 树上前缀和——某个节点到根的路径上的每个点的权值和 求法：$\mathrm{dfs}$时带参数传递下去即可 用法：$x\rightarrow y$的权值和 1. 点权：$s[x]+s[y]-s[\mathrm{lca}]-s[\mathrm{par}(\mathrm{lca})]$ 2. 边权： $s[x]+s[y]-2s[\mathrm{lca}]$ ### 树上差分 树上差分——某个节点对它到根的路径上的每个点的贡献 求法：修改$x\rightarrow y$上每个点/边的权值时： 1. 点权：$d[x]+=w,\ d[y]+=w,\ d[\mathrm{lca}]-=w,\ d[\mathrm{par}(\mathrm{lca})]-=w$ 2. 边权：$d[x]+=w,\ d[y]+=w,\ d[\mathrm{lca}]-=2w$ 用法：某个节点的权值即为它子树所有节点的差分和 ### 点权和边权 我们的树上前缀和与树上差分（还有树链剖分，小声）都是基于点权的。那么如果遇到边权的问题，如何解决呢？ 当然是把边权分配到点上了啊。由于每个点的父节点是唯一的，因此每个点到父节点的连边是唯一的。那么，我们把边权分配到子节点上，也就是分配到深度较大的端点上，问题就解决了。