企业官网建设流程全解析

前置：P4719 【模板】动态 DP - 洛谷

默认你已经会线段树版本的动态 DP：【题解】P4719 【模板】动态 DP（线段树版本）-CSDN博客

0.回顾

前面我们利用树链剖分将树变成了若干条重链，再对每条链独立建立线段树。

线段树的每个叶子维护一个转移矩阵。

修改时，先在线段树内更新，然后通过链与链之间的轻边向上“跳”。

这个算法时间复杂度单次：

第一个来自线段树内部维护链信息的复杂度。

第二个来自修改点后，沿着轻边向上跳的路径长度，因为保证轻边数量是的。

那么，既然我们无法避免轻边的数量，那能不能想办法把线段树的那个优化掉。

从而达到理论最优的呢？

1.介绍 GBBT

全局平衡二叉树（Global Balanced Binary Tree, GBBT）是一种巧妙的静态数据结构，

它被设计用来解决动态DP问题，可以将传统树链剖分加线段树的复杂度，

优化到理想的，同时兼具 LCT 的高效和树剖的实现便捷性。

以下为该算法流程：

首先进行一次树链剖分，找出每个点的重儿子。

对于每个点，定义一个权值，也就是该点的轻子树大小之和 + 1。

对于每条重链上的节点序列，按照它们的值寻找带权中点。

即左右两侧权值和尽可能平衡的点，将该点作为这棵二叉搜索树的根，然后递归处理左右序列。

那为什么这能保证树高是？

• 走轻边：根据树链剖分的性质，从任意节点向上。

• 每经过一条轻边，所在子树大小至少翻倍，因此轻边数量是。

• 走重边：在 GBBT 内向上走一条重边时，由于我们的带权中点选取策略。

• 当前节点在GBBT 中的子树大小至少翻倍，因此重边数量也是。

2.代码

#include <bits/stdc++.h> using namespace std; #define int long long // 最方便 const int N = 1e6 + 10; const int inf = 0x3f3f3f3f; int n, m; int a[N]; vector<int> G[N]; int fa[N], siz[N], son[N]; // 原树父亲、子树大小、重儿子 int f[N][2]; // 考虑节点 x 不选 / 选 的 DP 贡献值 // 和线段树不同的是，我们新建了 g 数组来辅助处理 // 实际逻辑和线段树版本是一样的，g 数组不起任何实际作用，只帮助理解 int g[N][2]; // 只考虑节点 x 的所有轻儿子（不包括重儿子）时 x 不选/选的 DP 贡献值 int gfa[N]; // GBBT 中的父亲 int ls[N], rs[N]; // GBBT 左右儿子 struct Matrix { int g[2][2]; Matrix() { memset(g, -0x3f, sizeof(g)); } void change(int g0, int g1) { g[0][0] = g[0][1] = g0; g[1][0] = g1; g[1][1] = -inf; } Matrix operator * (const Matrix &b) const { Matrix c; for (int i = 0; i < 2; i ++) for (int j = 0; j < 2; j ++) for (int k = 0; k < 2; k ++) c.g[i][j] = max(c.g[i][j], g[i][k] + b.g[k][j]); return c; } } mt[N], tr[N]; // 第一次 DFS：求 fa, siz, son, 静态 DP void dfs(int x) { siz[x] = 1; f[x][1] = a[x]; g[x][0] = 0; // 初始化轻儿子贡献 g[x][1] = a[x]; for (int y : G[x]) if (y != fa[x]) { fa[y] = x; dfs(y); siz[x] += siz[y]; if (siz[y] > siz[son[x]]) { son[x] = y; } f[x][0] += max(f[y][0], f[y][1]); f[x][1] += f[y][0]; } } int b[N], bs[N]; // b[]：重链节点序列（按深度从小到大），bs[]：顺着重链权值前缀和 // GBBT 重链内处理 // 传参：当前处理的重链节点序列区间 [l, r] // 返回值：构建出的子树的根节点编号 int g_build(int l, int r) { // 递归边界：区间只有一个节点，直接作为叶子返回 if (l == r) { tr[b[l]] = mt[b[l]]; // 该节点的矩阵就是它自己的转移矩阵 return b[l]; } // 二分寻找带权中点 int L = l, R = r, pm = l; int len = bs[r] - bs[l - 1]; // len：当前区间所有节点的权值总和 // 二分查找带权中点：让左半部分的权值和尽量接近总权值的一半 // 这样能保证左右子树平衡，路径长度 O(log n) while (L < R) { int mid = (L + R) >> 1; // 检查 [l, mid] 区间的权值和是否 ≤ 总权值的一半 if ((bs[mid] - bs[l - 1]) * 2 <= len) { L = mid + 1; // 可以继续右移，让左半更大 pm = mid; } else { R = mid - 1; // 左半太大，需要左移 } } // 以带权中点 pm 作为根节点 int rt = b[pm]; // 取出中点对应的节点编号作为根 tr[rt] = mt[rt]; // 初始矩阵为当前节点的转移矩阵 // 递归构建左右子树 // 构建左子树：[l, pm - 1]（深度更浅的节点） if (l <= pm - 1) { ls[rt] = g_build(l, pm - 1); // 递归构建，左儿子指向子树根 gfa[ls[rt]] = rt; // 设置左儿子在 GBBT 中的父亲为 rt tr[rt] = tr[ls[rt]] * tr[rt]; // 矩阵乘法顺序：左子树（浅层）× 当前节点 // 因为中序遍历是从浅到深，所以左子树在前 } // 构建右子树：[pm + 1, r]（深度更深的节点） if (r >= pm + 1) { rs[rt] = g_build(pm + 1, r); // 递归构建，右儿子指向子树根 gfa[rs[rt]] = rt; // 设置右儿子在 GBBT 中的父亲为 rt tr[rt] = tr[rt] * tr[rs[rt]]; // 矩阵乘法顺序：当前节点 × 右子树（深层） // 中序遍历顺序：左 -> 中 -> 右，所以右子树在后 } return rt; // 返回当前子树的根节点 } // 处理整棵树轻链间的连接，和重链节点序列和前缀和 int build(int u) { int v = u, tp = 0; // 处理所有轻子树，并计算当前节点的轻儿子贡献（使用静态 f） while (v) { int g0 = 0, g1 = a[v]; // g0 不选 v，g1 强制选 v for (int y : G[v]) { if (y != fa[v] && y != son[v]) { g0 += max(f[y][0], f[y][1]); g1 += f[y][0]; } } g[v][0] = g0; g[v][1] = g1; mt[v].change(g0, g1); // 递归构建轻子树的 GBBT，并通过 gfa 连接到 v for (int y : G[v]) { if (y != fa[v] && y != son[v]) { int lcrt = build(y); gfa[lcrt] = v; } } v = son[v]; // 下一个重儿子 } // 收集当前重链节点 while (u) { b[++ tp] = u; bs[tp] = bs[tp - 1] + siz[u] - siz[son[u]]; u = son[u]; } int RT = g_build(1, tp); // 有完整重链后处理 return RT; } // 判断节点 x 是否通过轻边连接到父亲，是 1，不是 0 // 在 GBBT 中，每个节点都有 gfa[x] 指向它的父节点 // 可能是同一条重链内的父亲，也可能是轻边连接的父链 // 但只有和父亲在同一条重链上，才会是父亲的左 / 右子节点 inline bool isLight(int u) { return gfa[u] && ls[gfa[u]] != u && rs[gfa[u]] != u; } // 动态 DP 更新 void update(int u, int k) { g[u][1] += k - a[u]; a[u] = k; mt[u].change(g[u][0], g[u][1]); // 沿 GBBT 向上更新 while (u) { Matrix old = tr[u]; // 重新计算当前节点的矩阵 // 当前节点的矩阵 = 左儿子矩阵 × 当前节点val × 右儿子矩阵 tr[u] = mt[u]; if (ls[u]) tr[u] = tr[ls[u]] * tr[u]; if (rs[u]) tr[u] = tr[u] * tr[rs[u]]; // 处理轻边更新 // 如果 u 是通过轻边连接到父节点的（即 u 是一条重链的根） // 那么 u 这棵子树的 DP 值发生了变化，需要更新父节点的 g 值 if (isLight(u)) { // 计算 u 子树在 不选 / 选根节点 时的最大权值（即整条重链的 DP 结果） // 注意：old 和 tr 中的 g[0][0] 表示子树根不选时的最大权 // g[1][0] 表示子树根选时的最大权 int oldAns = max(old.g[0][0], old.g[1][0]); // 更新前的整棵子树 DP 值 int newAns = max(tr[u].g[0][0], tr[u].g[1][0]); // 更新后的整棵子树 DP 值 // 更新父节点的 g[0]（父节点不选时，这个轻儿子可任意） // 父节点不选时，轻儿子贡献增加：newAns - oldAns g[gfa[u]][0] += newAns - oldAns; // 更新父节点的 g[1]（父节点选时，这个轻儿子必须不选） // 父节点选时，轻儿子必须不选，所以只取 g[0][0]（根节点不选的情况） g[gfa[u]][1] += tr[u].g[0][0] - old.g[0][0]; // 因为父节点的g值变了，需要重新构造父节点的转移矩阵 mt[gfa[u]].change(g[gfa[u]][0], g[gfa[u]][1]); } // 继续向上跳，到 GBBT 中的父节点 u = gfa[u]; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> a[i]; for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } dfs(1); // 第一次 DFS：求 fa, siz, son, 静态 DP int root = build(1); int last = -1; while (m--) { int x, y; cin >> x >> y; if (last != -1) { // 洛谷模版题要求强制在线异或 x ^= last; } update(x, y); int ans = max(tr[root].g[0][0], tr[root].g[1][0]); cout << ans << '\n'; last = ans; } return 0; }

3.到底和线段树比快哪了？