树上前缀和

当题目多次询问树上的一些路径的权值之和，此时可以考虑使用树上前缀和。这里所说的树上的路径可以类比为一维序列的区间。

树上前缀和分为点前缀和和边前缀和。

设 $su{m}_i$ 表示结点 $i$ 到根节点的权值总和，$f{a}_i$ 表示 $i$ 的父节点。

• 点权：$x,y$ 路径上的和为：$su{m}_x+su{m}_y-su{m}_{lca}-su{m}_{f{a}_{lca}}$
• 边权：$x,y$ 路径上的和为：$su{m}_x+su{m}_y-2\ast su{m}_{lca}$

树上差分

树上差分是对树上的某一段路径进行差分操作，这里所说的路径可以类比为一维数组的区间。树上差分常用在题目要求对树上的一些路径进行加法操作，之后询问某条边或某个点经过操作后的值。

树上差分分为点差分和边差分。

点差分

点差分要解决的问题是将树上 $s$ 和 $t$ 路径上的所有点的权值增加 $k$，最后询问点权最大的点是多少？

设 $d$ 为差分数组，$f{a}_i$ 表示 $i$ 的父节点， $lca$ 表示 $s$ 和 $t$ 的最近公共祖先，则上述操作具体实现为：

$$\begin{gathered} d_s=d_s+k \\ {d}_t=d_t+k \\ {d}_{f{a}_{lca}}=d_{f{a}_{lca}}-k \\ {d}_{lca}=d_{lca}-k \end{gathered}$$

之后可使用 DFS 计算任意节点的权值（该节点权值等于其本身及其所有子节点的权值之和）。

边差分

边差分要解决的问题是将树上 $s$ 和 $t$ 路径上的所有边权增加 $k$，最后询问边权最大的边是多少？

设 $d$ 为差分数组， $lca$ 表示 $s$ 和 $t$ 的最近公共祖先，则上述操作具体实现为：

$$\begin{gathered} d_s=d_s+k \\ {d}_t=d_t+k \\ {d}_{lca}=d_{lca}-2\ast k \end{gathered}$$