# 树上前缀和 --- 设 $sum_i$ 表示结点 $i$ 到根节点的权值总和。 然后： - 若是点权，$x,y$ 路径上的和为 $sum_x + sum_y - sum_{lca} - sum_{{fa}_{lca}}$。 - 若是边权，$x,y$ 路径上的和为 $sum_x + sum_y - 2\cdot sum_{lca}$。 LCA 的求法参见 [最近公共祖先](../graph/lca.md)。 --- ### 树上差分 树上差分可以理解为对树上的某一段路径进行差分操作，这里的路径可以类比一维数组的区间进行理解。例如在对树上的一些路径进行频繁操作，并且询问某条边或者某个点在经过操作后的值的时候，就可以运用树上差分思想了。 树上差分通常会结合 [树基础](../graph/tree-basic.md) 和 [最近公共祖先](../graph/lca.md) 来进行考察。树上差分又分为 **点差分** 与 **边差分**，在实现上会稍有不同。 --- #### 点差分 举例：对树上的一些路径 $\delta(s_1,t_1), \delta(s_2,t_2), \delta(s_3,t_3)\dots$ 进行访问，问一条路径 $\delta(s,t)$ 上的点被访问的次数。 对于一次 $\delta(s,t)$ 的访问，需要找到 $s$ 与 $t$ 的公共祖先，然后对这条路径上的点进行访问（点的权值加一），若采用 DFS 算法对每个点进行访问，由于有太多的路径需要访问，时间上承受不了。这里进行差分操作： $$ \begin{aligned} &d_s\leftarrow d_s+1\\ &d_{lca}\leftarrow d_{\textit{lca}}-1\\ &d_t\leftarrow d_t+1\\ &d_{f(\textit{lca})}\leftarrow d_{f(\textit{lca})}-1\\ \end{aligned} $$ 其中 $f(x)$ 表示 $x$ 的父亲节点，$d_i$ 为点权 $a_i$ 的差分数组。 ---  可以认为公式中的前两条是对蓝色方框内的路径进行操作，后两条是对红色方框内的路径进行操作。不妨令 $\textit{lca}$ 左侧的直系子节点为 $\textit{left}$。那么有 $d_{\textit{lca}}-1=a_{\textit{lca}}-(a_{\textit{left}}+1)$，$d_{f(\textit{lca})}-1=a_{f(\textit{lca})}-(a_{\textit{lca}}+1)$。可以发现实际上点差分的操作和上文一维数组的差分操作是类似的。 --- #### 边差分 若是对路径中的边进行访问，就需要采用边差分策略了，使用以下公式： $$ \begin{aligned} &d_s\leftarrow d_s+1\\ &d_t\leftarrow d_t+1\\ &d_{\textit{lca}}\leftarrow d_{\textit{lca}}-2\\ \end{aligned} $$  由于在边上直接进行差分比较困难，所以将本来应当累加到红色边上的值**向下移动到附近的点里**，那么操作起来也就方便了。对于公式，有了点差分的理解基础后也不难推导，同样是对两段区间进行差分。 --- ### 如果初始时各点的点权不为0，怎么做？ 1. 先计算出各点点权的差分值： - 叶子结点的差分值 = 自己的点权 - 其他节点的差分值 = 父权-子权和 2. 然后做多次的差分操作 3. 最后计算**节点差分值的子树和。** --- ### 例题 [洛谷 3128 最大流](https://www.luogu.com.cn/problem/P3128) FJ 给他的牛棚的 $N(2 \le N \le 50,000)$ 个隔间之间安装了 $N-1$ 根管道，隔间编号从 $1$ 到 $N$。所有隔间都被管道连通了。 FJ 有 $K(1 \le K \le 100,000)$ 条运输牛奶的路线，第 $i$ 条路线从隔间 $s_i$ 运输到隔间 $t_i$。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。 --- 需要统计每个点经过了多少次，那么就用树上差分将每一次的路径上的点加一，可以很快得到每个点经过的次数。这里采用倍增法计算 LCA，最后对 DFS 遍历整棵树，在回溯时对差分数组求和就能求得答案了。 --- ```cpp #include <algorithm> #include <iostream> using namespace std; constexpr int MAXN = 50010; struct node { int to, next; } edge[MAXN << 1]; int fa[MAXN][30], head[MAXN << 1]; int power[MAXN]; int depth[MAXN], lg[MAXN]; int n, k, ans = 0, tot = 0; void add(int x, int y) { // 加边 edge[++tot].to = y; edge[tot].next = head[x]; head[x] = tot; } void dfs(int now, int father) { // dfs求最大压力 fa[now][0] = father; depth[now] = depth[father] + 1; for (int i = 1; i <= lg[depth[now]]; ++i) fa[now][i] = fa[fa[now][i - 1]][i - 1]; for (int i = head[now]; i; i = edge[i].next) if (edge[i].to != father) dfs(edge[i].to, now); } int lca(int x, int y) { // 求LCA，最近公共祖先 if (depth[x] < depth[y]) swap(x, y); while (depth[x] > depth[y]) x = fa[x][lg[depth[x] - depth[y]] - 1]; if (x == y) return x; for (int k = lg[depth[x]] - 1; k >= 0; k--) { if (fa[x][k] != fa[y][k]) x = fa[x][k], y = fa[y][k]; } return fa[x][0]; } // 用dfs求最大压力，回溯时将子树的权值加上 void get_ans(int u, int father) { for (int i = head[u]; i; i = edge[i].next) { int to = edge[i].to; if (to == father) continue; get_ans(to, u); power[u] += power[to]; } ans = max(ans, power[u]); } int main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> k; int x, y; for (int i = 1; i <= n; i++) { lg[i] = lg[i - 1] + (1 << lg[i - 1] == i); } for (int i = 1; i <= n - 1; i++) { // 建图 cin >> x >> y; add(x, y); add(y, x); } dfs(1, 0); int s, t; for (int i = 1; i <= k; i++) { cin >> s >> t; int ancestor = lca(s, t); // 树上差分 power[s]++; power[t]++; power[ancestor]--; power[fa[ancestor][0]]--; } get_ans(1, 0); cout << ans << '\n'; return 0; } ``` --- ## 习题 *** 树上前缀和： - [LOJ 10134.Dis](https://loj.ac/problem/10134) - [LOJ 2491. 求和](https://loj.ac/problem/2491) *** 树上差分： - [洛谷 3128 最大流](https://www.luogu.com.cn/problem/P3128) - [JLOI2014 松鼠的新家](https://loj.ac/problem/2236) - [NOIP2015 运输计划](http://uoj.ac/problem/150) - [NOIP2016 天天爱跑步](http://uoj.ac/problem/261)