01 树上 前缀和 及 差分

根据 $dfs$ 序对树的节点进行差分操作
$O(1)$ 复杂度实现某个点权集合或边权集合加一个值
$O(n)$ 复杂度求出所有的点权 / 边权

前缀和

void get(int u, int f){
	for(auto v : G[u]){
		if(v == f) conitnue;
		get(v, u);
		d[u] += d[v];
	}
}

树上差分

树上差分分为点差分和边差分，通常结合树基础和最近公共祖先来出问题

点差分

$(a,b)$ 代表 $a$ 到 $b$ 点的最短路径上的点的权值之和
$s[x]$ 表示 $x$ 点 到 总树的根节点的路径上的权值之和
$s[1]=w[1]$

(a, b) = s[a] + s[y] - s[lca(x, y)] - s[f[lca(x, y)]];

边差分

其实和点差分差不多

(a, b) = s[a] + s[b] - 2 * s[lca(a, b)];