樹上前綴和

求前綴和，我們一般默認\(w[i]\) 表示該節點到根節點的權值和，采用自頂向下更新。

點權前綴

x到y路徑上的和為:

邊權前綴

x到y的路徑上的和為:

樹上差分學習

? 樹上差分可以理解為對樹上某一段路徑進行差分操作，這里的路徑可以類比一維數組的區間進行理解。 例如在對樹上的一些路徑進行頻繁操作，并且詢問某條邊或某個點在經過操作后的值的時候，就可以運用樹上差分思想了。

? 樹上差分通常會結合 樹基礎 和 最近共公共祖先進行考察。 樹差分又分為 點差分 和 邊差分， 在實現上會稍有不同。

點差分

注意樹上差分+前綴我們需要自底向上更新，\(w[i]\) 表示以\(i\)節點為根的權值和

例題：Max Flow P

#include <bits/stdc++.h>

using i64 = long long;

const int N = 5e5 + 10, M = N;

int n, k;

int h[N], e[M], ne[M], w[M], idx;

int depth[N], fa[N][17], sum[N], par[N], ans;

void add(int a, int b) {
	ne[idx] = h[a], h[a] = idx, e[idx ++] = b;	
}

void dfs(int u, int father, int dep) {
	depth[u] = dep;

	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];

		if (v == father) continue;

		fa[v][0] = u;

		for (int k = 1; k <= 16; k ++) {
			fa[v][k] = fa[fa[v][k - 1]][k - 1];
		}

		dfs(v, u, dep + 1);
	}
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) std::swap(a, b);

	for (int k = 16; k >= 0; k --) {
		if (depth[fa[a][k]] >= depth[b]) {
			a = fa[a][k];
		}
	}

	if (a == b) return a;

	for (int k = 16; k >= 0; k --) {
		if (fa[a][k] != fa[b][k]) {
			a = fa[a][k];
			b = fa[b][k];	
		}
	}

	return fa[a][0];
}

int dfs2(int u, int fa) {
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];

		if (v == fa) continue;

		int s = dfs2(v, u);

		sum[u] += s;
	}

	ans = std::max(ans, sum[u]);

	return sum[u];
}

int main() {
	memset(h, -1, sizeof h);
	
	std::cin >> n >> k;	

	for (int i = 1; i < n; i ++) {
		int x, y;
		
		std::cin >> x >> y;

		add(x, y);	
		add(y, x);
	}

	depth[0] = 0;
	dfs(1, -1, 1);

	while (k --) {
		int x, y;

		std::cin >> x >> y;

		int anc = lca(x, y);

		sum[x] += 1;
		sum[y] += 1;
		sum[anc] -= 1;

		if (fa[anc][0])
			sum[fa[anc][0]] -= 1;
	}

	dfs2(1, -1);

	std::cout << ans;
}

邊差分

對于邊差分，由于樹是拓撲結構，我們用向下的一條邊所指向的點來表達邊，這樣很簡單就能推出上述公式。

例題: 闇の連鎖

#include <bits/stdc++.h>

using i64 = long long;

const int N = 1e5 + 10, M = 2 * N;

int n, m;

int h[N], e[M], ne[M], w[M], idx;

int fa[N][18], depth[N], sum[M];

i64 ans;

void add(int a, int b) {
	ne[idx] = h[a], h[a] = idx, e[idx ++] = b;
}

void dfs(int u, int father, int dep) {
	depth[u] = dep;

	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];

		if (v == father) continue;

		depth[v] = depth[u] + 1;

		fa[v][0] = u;

		for (int k = 1; k <= 17; k ++) {
			fa[v][k] = fa[fa[v][k - 1]][k - 1];
		}

		dfs(v, u, dep + 1);
	}
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) std::swap(a, b);

	for (int k = 17; k >= 0; k --) {
		if (depth[fa[a][k]] >= depth[b]) {
			a = fa[a][k];
		}
	}

	if (a == b) return b;

	for (int k = 17; k >= 0; k --) {
		if (fa[a][k] != fa[b][k]) {
			a = fa[a][k];
			b = fa[b][k];
		}
	}

	return fa[a][0];
}

int dfs2(int u, int fa) {
	int res = sum[u];

	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];

		if (v == fa) continue;

		int s = dfs2(v, u);

		if (s == 0) ans += m;
		else if (s == 1) ans ++;

		res += s;
	}

	return res;
}

int main() {
	memset(h, -1, sizeof h);

	std::cin >> n >> m;

	for (int i = 1; i <= n - 1; i ++) {
		int x, y;
		
		std::cin >> x >> y;	

		add(x, y);
		add(y, x);
	}

	depth[0] = 0;

	dfs(1, -1, 1);

	for (int i = 1; i <= m; i ++) {
		int x, y;

		std::cin >> x >> y;

		sum[x] += 1;
		sum[y] += 1;
		sum[lca(x, y)] -= 2;
	}
	

	dfs2(1, -1);

	std::cout << ans;
}

例題2:松鼠的新家

#include <bits/stdc++.h>

using i64 = long long;

const int N = 3e5 + 10, M = N * 2;

int n, m;

int h[N], e[M], ne[M], idx;

int fa[N][19], depth[N], sum[M];

int a[N];

i64 ans;

void add(int a, int b) {
	ne[idx] = h[a], h[a] = idx, e[idx ++] = b;
}

void dfs(int u, int father, int dep) {
	depth[u] = dep;

	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];

		if (v == father) continue;

		depth[v] = depth[u] + 1;

		fa[v][0] = u;

		for (int k = 1; k <= 18; k ++) {
			fa[v][k] = fa[fa[v][k - 1]][k - 1];
		}

		dfs(v, u, dep + 1);
	}
}

int lca(int a, int b) {
	if (depth[a] < depth[b]) std::swap(a, b);

	for (int k = 18; k >= 0; k --) {
		if (depth[fa[a][k]] >= depth[b]) {
			a = fa[a][k];
		}
	}

	if (a == b) return b;

	for (int k = 18; k >= 0; k --) {
		if (fa[a][k] != fa[b][k]) {
			a = fa[a][k];
			b = fa[b][k];
		}
	}

	return fa[a][0];
}

int dfs2(int u, int fa) {
	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];

		if (v == fa) continue;

		sum[u] += dfs2(v, u);
	}

	return sum[u];
}


int main() {
	memset(h, -1, sizeof h);

	std::cin >> n;

	for (int i = 1; i <= n; i ++) {
		std::cin >> a[i];
	}

	for (int i = 1; i <= n - 1; i ++) {
		int x, y;
		
		std::cin >> x >> y;	

		add(x, y);
		add(y, x);
	}

	depth[0] = 0;
	dfs(1, -1, 1);

	for (int i = 2; i <= n; i ++) {
		int x = a[i - 1], y = a[i];

		sum[x] += 1;
		
		sum[y] += 1;

		int anc = lca(x, y);

		sum[anc] -= 1;

		sum[fa[anc][0]] -= 1;
	}	
	
	dfs2(1, -1);

	sum[a[1]] ++;

	for (int i = 1; i <= n; i ++) {
		std::cout << sum[i] - 1 << "\n";
	}
}