树上前缀和与树上差分

树上前缀和与树上差分都是树链剖分优秀的离线替代品，配合树状数组还可以进一步处理在线的情况。

树上前缀和

树上前缀和——某个节点到根的路径上的每个点的权值和

求法：$\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$

用法：某个节点的权值即为它子树所有节点的差分和

点权和边权

我们的树上前缀和与树上差分（还有树链剖分，小声）都是基于点权的。那么如果遇到边权的问题，如何解决呢？

当然是把边权分配到点上了啊。由于每个点的父节点是唯一的，因此每个点到父节点的连边是唯一的。那么，我们把边权分配到子节点上，也就是分配到深度较大的端点上，问题就解决了。