当前位置： 首页 > news >正文

【P3128】树上路径点权加1｜倍增LCA + 树上差分

news 2026/7/15 19:54:21

【P3128】树上路径点权加1｜倍增LCA + 树上差分

一、题目题意

题意简述

  1. 给定一棵 $N$ 个节点的无根树（$N-1$ 条双向边，全部牛棚连通）；
  2. 共 $K$ 次操作，每次给出两点 $s,t$，将树上 $s$ 到 $t$ 整条路径上所有点的流量 $+1$；
  3. 求所有节点中，流量数值的最大值。

核心规则

一条路径 $s \to t$ 包含：起点$s$、终点$t$、两点之间所有中转牛棚，全部计数+1。

数据范围

$2\le N \le 5\times 10^4,\ 1\le K \le 1\times 10^5$，暴力遍历路径会超时，必须使用树上差分优化。

二、两大核心算法原理

1. 倍增LCA

快速求出树上两点 $s,t$ 的最近公共祖先 $l=\text{lca}(s,t)$，拆分路径：

$$s \to t = s \to l + t \to l - l$$

2. 树上点差分（路径区间+1模板）

若要给路径 $s \to t$ 所有点权值 $+1$，设 $l=\text{lca}(s,t)$，树上差分修改规则：

power[s] += 1
power[t] += 1
power[l] -= 1
power[ fa[l][0] ] -= 1

原理：子树回溯求和时，仅 $s\sim t$ 路径上的点会被多累计1次，其余点抵消为0。全部操作完成后，执行一次后序DFS子树累加，power[u] 即为节点 $u$ 总流量。
请添加图片描述

三、完整解题步骤

步骤1：建图

读取节点数 $N$、路径操作次数 $m$；循环读入 $N-1$ 条双向边，用链式前向星存储无向树。

步骤2：DFS预处理倍增LCA数组

从根节点1出发深搜：

  1. 记录每个节点深度 dep[u]；
  2. 预处理倍增祖先数组 fa[u][i]，fa[u][i] 代表 $u$ 向上跳 $2^i$ 步的祖先，用于快速LCA查询。

步骤3：批量处理K条路径操作

循环 $m$ 次，每组读入 $s,t$：

  1. 调用lca(s,t)求出两点公共祖先$l$；
  2. 套用树上差分四点修改公式，更新power数组标记。

步骤4：后序DFS统计子树贡献，求最大值

第二次DFS遍历整棵树：

  1. 递归处理所有子节点，将子节点power[v]累加到父节点power[u]；
  2. 遍历过程同步维护全局最大值ans；

步骤5：输出答案

打印全局最大流量ans。

四、完整AC代码

#include <cstdio>
#include <algorithm>
using namespace std;const int N = 50005, M = 2 * N;
int h[N], to[M], ne[M], tot;
int dep[N], fa[N][22];
int n, m, ans, power[N];void add(int x, int y) { // 链式前向星双向加边to[++tot] = y;ne[tot] = h[x];h[x] = tot;
}void dfs(int u, int f) { // 倍增LCA预处理DFSdep[u] = dep[f] + 1;fa[u][0] = f;for (int i = 0; fa[u][i]; ++i)fa[u][i + 1] = fa[fa[u][i]][i];for (int i = h[u]; i; i = ne[i])if (to[i] != f) dfs(to[i], u);
}int lca(int u, int v) { // 倍增求两点最近公共祖先if (dep[u] > dep[v]) swap(u, v);// 将v跳到与u同一深度for (int i = 20; i >= 0; --i)if (dep[u] <= dep[v] - (1 << i)) v = fa[v][i];if (u == v) return u;// 同步向上跳跃for (int i = 20; i >= 0; --i)if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];return fa[u][0];
}void dfs2(int u, int f) { // 后序子树求和，统计最大流量for (int i = h[u]; i; i = ne[i]) {int v = to[i];if (v == f) continue;dfs2(v, u);power[u] += power[v];}ans = max(ans, power[u]);
}int main() {scanf("%d%d", &n, &m);for (int i = 1, x, y; i < n; ++i) {scanf("%d%d", &x, &y);add(x, y); add(y, x);}dfs(1, 0);// 处理m次路径区间+1for (int i = 1, x, y; i <= m; ++i) {scanf("%d%d", &x, &y);int l = lca(x, y);++power[x]; ++power[y];--power[l]; --power[fa[l][0]];}dfs2(1, 0);printf("%d\n", ans);return 0;
}

五、代码分段详解

1. 全局常量与数组

const int N = 50005, M = 2 * N;
int h[N], to[M], ne[M], tot;
int dep[N], fa[N][22];
int n, m, ans, power[N];
  • N=5e4：节点上限；M=2*N 双向边开双倍空间；
  • fa[N][22]：倍增数组，$2^{20}$ 覆盖最大深度；
  • dep[]：节点深度；power[]：树上差分数组，记录流量标记；
  • ans：保存全局最大流量。

2. 链式前向星加边

void add(int x, int y) {to[++tot] = y;ne[tot] = h[x];h[x] = tot;
}

无向树每条边存两次，构建双向连通关系。

3. 预处理倍增数组 dfs

void dfs(int u, int f) {dep[u] = dep[f] + 1;fa[u][0] = f;for (int i = 0; fa[u][i]; ++i)fa[u][i + 1] = fa[fa[u][i]][i];for (int i = h[u]; i; i = ne[i])if (to[i] != f) dfs(to[i], u);
}
  1. 初始化父节点fa[u][0]与深度；
  2. 递推倍增祖先：$2^{i+1}$ 祖先 = $2^i$ 祖先的 $2^i$ 祖先；
  3. 递归遍历子树。

4. 倍增LCA函数

int lca(int u, int v) {if (dep[u] > dep[v]) swap(u, v);for (int i = 20; i >= 0; --i)if (dep[u] <= dep[v] - (1 << i)) v = fa[v][i];if (u == v) return u;for (int i = 20; i >= 0; --i)if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];return fa[u][0];
}

标准倍增LCA流程：拉平深度→同步上跳→返回公共祖先。

5. 子树求和dfs2

void dfs2(int u, int f) {for (int i = h[u]; i; i = ne[i]) {int v = to[i];if (v == f) continue;dfs2(v, u);power[u] += power[v];}ans = max(ans, power[u]);
}

后序遍历，先算所有子节点，再把子节点流量累加到父节点；遍历同时更新全局最大值。

6. main主函数流程

  1. 读入 $n,m$，循环建双向树；
  2. 根1执行DFS预处理倍增；
  3. 循环处理每条路径，LCA配合树上差分打标记；
  4. DFS2后序合并子树流量，得到每个节点总流量；
  5. 输出最大流量ans。

六、题型总结

  1. 模型定位：倍增LCA + 树上点差分，树上路径区间更新经典模板；

  2. 树上差分记忆公式：路径$s \to t$ 全体+1

$$power[s]++,power[t]++,power[lca]--,power[fa[lca][0]]--$$

  1. 复杂度分析

    • 预处理LCA：$O(N\log N)$；
    • $m$ 次路径操作：每次LCA $O(\log N)$，总 $O(m\log N)$；
    • 子树求和DFS：$O(N)$；
      数据范围 $5\times104、1\times105$ 完全无超时；

  2. 拓展区分

    • 点差分：路径所有点修改，使用本题四标记公式；
    • 边差分：路径所有边修改，仅需修改两点+LCA两处标记。