学习笔记：全局平衡二叉树 GBBT
CGcgxyXY
·
·
算法·理论
叫法好像不少，我就按字面意思翻译成 Global Balanced Binary Tree 了，取首字母缩写 GBBT。
建议先了解重链剖分算法。
我写过一篇笔记，也可以看 OI Wiki。
下面默认读者已经了解了重链剖分。
无特殊说明时，可以简单认为维护的信息合并是 O(1) 的。
引入
先考虑一个树上问题：
我们知道，通过树链剖分可以把树上的一条路径转化成 dfs 序上 O(\log n) 个区间，再使用维护区间数据结构做这些操作即可。
以本题为例，把边权转到点上，使用线段树维护，一次操作的复杂度可以做到时间 O(\log^2 n)，同时空间是 O(n) 的。
如果你还会一个常数优化技巧：由于线段树只需要维护链，可以对每一条链单独开一棵线段树，做到 O(\sum \log len)，其中 len 是路径上一条重链的长度。
显然这样常数会变小，但是复杂度还是 O(\log^2 n) 的。
:::info[卡满复杂度的数据构造]
建立一棵 \sqrt n 个结点的二叉树。
对于每个结点到其儿子的边，我们将其替换成一条长度为 \sqrt n 长度的链。
这样一个节点到根平均会有 \frac{\log_2 n}{2} 个重链，每一个重链的长度至少是 O(\sqrt n) 的，线段树一次操作复杂度是 O(\log \sqrt n)=O(\log n) 的。
这样就被卡到了 O(\log^2 n) 的复杂度。
| 不过还是可以看出来，常数比直接在全局的线段树上查询要小。 |
使用这一种卡常方法，我们可以在一个线段树形成的“树”上描述一次操作的过程。
比如下图为一棵树和它的树链剖分，其中红边是重边，黑边是轻边。
下图是线段树形成的树。
其中一个线段树叶子上的数字是该位置对应原树上的节点编号。
重链链顶的轻边用虚线表示。
考虑操作的过程。
在路径 u,v 上面操作，就需要从 u,v 向上跳，做 O(\log n) 次重链上面的前缀操作，和 \operatorname{lca}(u,v) 所在重链上面的区间操作。
做一次 [top_u,u] 的前缀操作，时间是 O(d_u)，其中 d_u 是 u 在维护 u 重链的线段树上的深度，值是 O(\log len)。
做一次区间操作，时间是 O(h_{top_u})，其中 h_{top_u} 是 u 所在重链的线段树的高度，值是 O(\log len)。
考虑利用这个性质进行优化。
全局平衡二叉树 / Global Balanced Binary Tree (GBBT)
GBBT 是对每个重链开一棵线段树的改进，或者说是静态化的 LCT。
GBBT 的改进在于，对于每一条重链同样使用了二叉树维护，但是二叉树对链上区间根据权值进行划分，做到按照引入中方法连接起来的总体树高是 O(\log n) 的，并可以支持 O(n \log n) 的建树和 O(\log n) 的路径操作。
GBBT 中，一棵重链的二叉树维护这条重链按照深度从小到大排序的所有节点，并且按照权值划分子树。
GBBT 的二叉树可以选择 nodey 和 leafy，两种各有优劣。
:::info[什么是 nodey 和 leafy]
nodey-tree 的每一个节点维护节点本身的信息和子树的信息，每一个位置对应着一个节点的值和一个区间的值。
常见的 Treap、Splay 等一般也都是 nodey-tree。
leafy-tree 的每一个非叶子节点代表一个区间，只在叶子节点存值。
常见的线段树、WBLT 等都是 leafy-tree。
:::
nodey 的好处是空间是 1 倍的，坏处是一次 pushup 需要做两次信息合并，并且比较难写。
leafy 的好处是 pushup 只需要做一次合并，而且好写，坏处是空间 2 倍，并且高度也是 2 倍。
综合来看其实 nodey 更优秀一点（时空常数上），但是 leafy 很好写。
如果是特殊的操作（例如路径有一个端点是根），可以写 nodey，代码可以做到比较简洁。
nodey 的实现可以参考 OI wiki，这里介绍 leafy 的写法。
注：下文中 leafy-tree 指的是维护一条重链的二叉树，GBBT 指全局的二叉树。
在 GBBT 中，一个节点 u 的权值是 sz_u-sz_{son_u}，即 u 的轻子树大小和加上 u 本身的大小。
（这里认为 sz_0=0，叶子的重儿子为 0。）
对于一条重链，按照权值不断将链划分。
每次取带权中点将当前的区间划分成两个区间，使得两个区间的权值都在总权值的一半左右，最后得到一棵 leafy-tree。
下图为引入中图示树的每个节点的权值。
这棵树按照权值划分和线段树一致，但是只是特殊情况。
可以证明，如果把这些二叉树按照引入中的方式连接起来，全局的树高是 O(\log n) 的。
这里记二叉树上面的边是实边，连接重链二叉树之间的边（原树上的轻边）是虚边。
::::info[证明]
记 W_p 为当前 leafy-tree 上节点 p 子树中叶子的权值之和。
从这个二叉树上向上跳，如果是跳了一条实边，那么 W_p 会翻倍。
如果跳了一条虚边，W_p 不会下降。
:::info[为什么跳虚边权值不会下降]
跳之前的 W_p 是一条重链上的权值之和，其值等于链顶的子树大小。
:::
由于一个 leafy-tree 点的 $W_p$ 最多是 $n$（根所在重链的 leafy-tree 的根），那么经过的实边最多会有 $O(\log n)$ 条。
又由于轻边的性质，虚边最多有 $O(\log n)$ 条。
所以这棵树的高度是 $O(\log n)$ 的。
::::
这里给出建树的实现和解释。
#### 预处理
```cpp
vector<pair<int, int>> g[N];
int fa[N], wt[N], dep[N], sz[N], son[N];
void dfs1(int u, int pr){
fa[u] = pr;
dep[u] = dep[pr] + 1;
sz[u] = 1;
for (auto [v, w] : g[u]) if (v != pr){
wt[v] = w;
dfs1(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
}
}
```
和重链剖分一致，不多介绍。
#### 建树
```cpp
struct node {
int ls, rs;//左右儿子的编号
int mid;//区间中点
int mx;//区间最大值
int t1, t2;//t1 为加标记，t2 为赋值标记
void add(int x){//区间加
mx += x;
t1 += x;
}
void chg(int x){//区间赋值
mx = x;
t1 = 0;
t2 = x;
}
} t[N<<1];//注意 leafy-tree 需要两倍空间
int rt[N], tot;
//rt[u] 是 u 所在重链的 leafy-tree 的根节点编号，tot 为目前 GBBT 的总节点数
#define lc t[p].ls
#define rc t[p].rs
int top[N], pos[N], len[N];
//top[u] 为 u 所在链顶
//pos[u] 是 u 在重链的 leafy-tree 上的位置（中序遍历的序号，或深度排名）
//len[u] 是 u 所在重链的长度
void up(int p){//pushup
t[p].mx = max(t[lc].mx, t[rc].mx);//由于没有的儿子编号是 0，而 t[0].mx=0，所以计算 0 不会影响信息正确性
}
```
这部分用来存 GBBT，需要注意 leafy-tree 需要两倍空间。
建树时，从根开始 dfs，先对 $u$ 重链上所有节点的轻儿子递归建树，再把 $u$ 的重链拿出来建树。
同时需要计算出 $u$ 重链上的信息。
```cpp
int nod[N], cnt;
//nod[i] 用于临时保存 u 所在的重链，cnt 是当前重链长度
void dfs2(int u){
for (int x = u; x; x = son[x]) for (auto [y, w] : g[x]) if (y != fa[x] && y != son[x]) dfs2(y);//递归重链上节点的轻儿子
cnt = 0;
for (int x = u; x; x = son[x]) nod[++cnt] = x, pos[x] = cnt;//按照深度顺序加入重链节点，更新 pos[x]
nod[cnt + 1] = 0;//重置哨兵
int root = build(1, cnt);
for (int x = u; x; x = son[x]) rt[x] = root, top[x] = u, len[x] = cnt;//更新信息
}
```
其中 `build(l,r)` 用于建出 $[nod_l , nod_r]$ 这一段链的二叉树，返回根节点的编号。
下面是 `build(l,r)` 的实现。
```cpp
int build(int l, int r){
if (l == r){//leafy-tree 上叶子
int p = ++tot;
t[p].mid = l;
t[p].mx = wt[nod[l]];//构建叶子
t[p].t2 =-1;//覆盖标记初始化为特殊值
return p;
}
int L = l, R = r;
while (L < R){
int mid = (L + R) >> 1;
if (2 * (sz[nod[l]] - sz[nod[mid + 1]]) < sz[nod[l]] - sz[nod[r + 1]]) L = mid + 1;
else R = mid;
}
if (L == r)--L;//注意特判，不能有空区间
int p = ++tot;
t[p].mid = L;
lc = build(l, L), rc = build(L + 1, r);//递归左右区间建树
up(p);//更新信息
t[p].t2 =-1;//覆盖标记初始化为特殊值
return p;
}
```
注意二分的写法，由于一个结点的权值是 $sz_u-sz_{son_u}$，所以 $sz_{nod_i}$ 其实是重链上权值的后缀和。
全局数组 `sz[0]` 被初始化为 $0$，所以需要重置 `nod[cnt+1]=0`。
可以简化一点代码。
这样写的话，一条重链的操作就是简单的，和线段树几乎一模一样，只需要把 $mid$ 改成 leafy-tree 的带权中点即可。
:::info[例题实现]
```cpp
#define mid t[p].mid
void add(int p, int pl, int pr, int l, int r, int x){
if (l <= pl && pr <= r) return t[p].add(x);
down(p);
if (l <= mid) add(lc, pl, mid, l, r, x);
if (r > mid) add(rc, mid + 1, pr, l, r, x);
up(p);
}
void cov(int p, int pl, int pr, int l, int r, int x){
if (l <= pl && pr <= r) return t[p].chg(x);
down(p);
if (l <= mid) cov(lc, pl, mid, l, r, x);
if (r > mid) cov(rc, mid + 1, pr, l, r, x);
up(p);
}
int query(int p, int pl, int pr, int l, int r){
if (l <= pl && pr <= r) return t[p].mx;
int res = 0;
down(p);
if (l <= mid) res = max(res, query(lc, pl, mid, l, r));
if (r > mid) res = max(res, query(rc, mid + 1, pr, l, r));
return res;
}
```
:::
路径操作和重链剖分也几乎一样，只需要更改查询的参数，在 leafy-tree 上面查询。
:::info[例题实现]
```cpp
void add_link(int u, int v, int x){
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
add(rt[u], 1, len[u], 1, pos[u], x);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
if (u != v) add(rt[u], 1, len[u], pos[u] + 1, pos[v], x);
}
void cov_link(int u, int v, int x){
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
cov(rt[u], 1, len[u], 1, pos[u], x);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
if (u != v) cov(rt[u], 1, len[u], pos[u] + 1, pos[v], x);
}
int qry_link(int u, int v){
int res = 0;
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res = max(res, query(rt[u], 1, len[u], 1, pos[u]));
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
if (u != v) res = max(res, query(rt[u], 1, len[u], pos[u] + 1, pos[v]));
return res;
}
```
:::
以下给出例题的完整实现：
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 1e5 + 5, INF = 0x3f3f3f3f;
int n;
int eu[N], ev[N];
vector<pair<int, int>> g[N];
int fa[N], wt[N], dep[N], sz[N], son[N];
//这部分和重剖一致
void dfs1(int u, int pr){
fa[u] = pr;
dep[u] = dep[pr] + 1;
sz[u] = 1;
for (auto [v, w] : g[u]) if (v != pr){
wt[v] = w;
dfs1(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
}
}
struct node {
int ls, rs;
//左右儿子的编号
int mid;
//区间中点
int mx;
//区间最大值
int t1, t2;
//t1 为加标记，t2 为赋值标记
void add(int x){//区间加
mx += x;
t1 += x;
}
void chg(int x){//区间赋值
mx = x;
t1 = 0;
t2 = x;
}
}
t[N << 1];
//注意 leafy-tree 需要两倍空间
int rt[N], tot;
//rt[u] 是 u 所在重链的 leafy-tree 的根节点编号，tot 为目前 GBBT 的总节点数
#define lc t[p].ls
#define rc t[p].rs
int top[N], pos[N], len[N];
//top[u] 为 u 所在链顶
//pos[u] 是 u 在重链的 leafy-tree 上的位置（中序遍历的序号，或深度排名）
//len[u] 是 u 所在重链的长度
void up(int p){//pushup
t[p].mx = max(t[lc].mx, t[rc].mx); //由于没有的儿子编号是 0，而 t[0].mx=0，所以计算 0 不会影响信息正确性
}
void down(int p){//pushdown，注意这里 lazy-tag 是先赋值再加的形式
if (t[p].t2 !=-1){
if (lc) t[lc].chg(t[p].t2);
if (rc) t[rc].chg(t[p].t2);
t[p].t2 =-1;
}
if (t[p].t1){
if (lc) t[lc].add(t[p].t1);
if (rc) t[rc].add(t[p].t1);
t[p].t1 = 0;
}
}
int nod[N], cnt;
//nod[i] 用于临时保存 u 所在的重链，cnt 是当前重链长度
int build(int l, int r){
if (l == r){//leafy-tree 上叶子
int p = ++tot;
t[p].mid = l;
t[p].mx = wt[nod[l]];
//构建叶子
t[p].t2 =-1;
//覆盖标记初始化为特殊值
return p;
}
int L = l, R = r;
while (L < R){
int mid = (L + R) >> 1;
if (2 * (sz[nod[l]] - sz[nod[mid + 1]]) < sz[nod[l]] - sz[nod[r + 1]]) L = mid + 1;
else R = mid;
}
if (L == r)--L; //注意特判，不能有空区间
int p = ++tot;
t[p].mid = L;
lc = build(l, L), rc = build(L + 1, r); //递归左右区间建树
up(p); //更新信息
t[p].t2 =-1;
//覆盖标记初始化为特殊值
return p;
}
void dfs2(int u){
for (int x = u; x; x = son[x]) for (auto [y, w] : g[x]) if (y != fa[x] && y != son[x]) dfs2(y); //递归重链上节点的轻儿子
cnt = 0;
for (int x = u; x; x = son[x]) nod[++cnt] = x, pos[x] = cnt; //按照深度顺序加入重链节点，更新 pos[x]
nod[cnt + 1] = 0;
//重置哨兵
int root = build(1, cnt);
for (int x = u; x; x = son[x]) rt[x] = root, top[x] = u, len[x] = cnt; //更新信息
}
#define mid t[p].mid//mid 是区间带权中点，同时是左区间右端点
//以下的实现和普通的线段树几乎一致
void add(int p, int pl, int pr, int l, int r, int x){
if (l <= pl && pr <= r) return t[p].add(x);
down(p);
if (l <= mid) add(lc, pl, mid, l, r, x);
if (r > mid) add(rc, mid + 1, pr, l, r, x);
up(p);
}
void cov(int p, int pl, int pr, int l, int r, int x){
if (l <= pl && pr <= r) return t[p].chg(x);
down(p);
if (l <= mid) cov(lc, pl, mid, l, r, x);
if (r > mid) cov(rc, mid + 1, pr, l, r, x);
up(p);
}
int query(int p, int pl, int pr, int l, int r){
if (l <= pl && pr <= r) return t[p].mx;
int res = 0;
down(p);
if (l <= mid) res = max(res, query(lc, pl, mid, l, r));
if (r > mid) res = max(res, query(rc, mid + 1, pr, l, r));
return res;
}
//以下的实现和树剖+线段树也几乎一致
void add_link(int u, int v, int x){
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
add(rt[u], 1, len[u], 1, pos[u], x);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
if (u != v) add(rt[u], 1, len[u], pos[u] + 1, pos[v], x);
}
void cov_link(int u, int v, int x){
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
cov(rt[u], 1, len[u], 1, pos[u], x);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
if (u != v) cov(rt[u], 1, len[u], pos[u] + 1, pos[v], x);
}
int qry_link(int u, int v){
int res = 0;
while (top[u] != top[v]){
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res = max(res, query(rt[u], 1, len[u], 1, pos[u]));
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
if (u != v) res = max(res, query(rt[u], 1, len[u], pos[u] + 1, pos[v]));
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
rep(i, 1, n - 1){
int u, v, w;
cin >> u >> v >> w;
eu[i] = u, ev[i] = v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs1(1, 0);
dfs2(1);
string op;
int x, y, z;
while (cin >> op){
if (op == "Stop") break;
if (op == "Change"){
cin >> x >> y;
cov_link(eu[x], ev[x], y);
}
else if (op == "Cover"){
cin >> x >> y >> z;
cov_link(x, y, z);
}
else if (op == "Add"){
cin >> x >> y >> z;
add_link(x, y, z);
}
else {
cin >> x >> y;
cout << qry_link(x, y) << '\n';
}
}
return 0;
}
```
:::
### 复杂度证明
以上面例题的代码为例，nodey-tree 的证明也是类似的。
#### 建树
如果设 $len$ 是当前区间的长度，$k$ 是左区间的长度，那么有 $T(len)=O(\log len)+T(k)+T(len-k)$。
由于 $k$ 的值没有保证，但是 $W$ 是减半的，所以最多只会递归 $O(\log n)$ 层。
记每一层的若干个区间长度是 $L_i$。
那么一层的复杂度就是 $O(\sum \log L_i) \leq O(len)$。
所以建立一条重链的 leafy-tree 是 $O(len \log n)$ 的。
所以复杂度最坏 $O(\sum len \log n)=O(n \log n)$。
#### 路径操作
记 $d_u$ 为 GBBT 上节点 $u$ 的深度，$rt_u$ 为节点 $u$ 所在重链的 leafy-tree 的根节点编号。
那么重链上一次 $[top_u,u]$ 前缀操作的时间复杂度就是 $O(d_u-d_{rt_u})$。
因为如果 $[top_u,u]$ 在当前左区间内，那么会直接递归左区间；否则递归的左区间会被完全包含，直接返回，然后再递归右区间。
这样经过的节点总数就是 $rt_u$ 和 $u$ 对应叶子的距离，就是 $O(d_u-d_{rt_u})$。
本质上就是从 $rt_u$ 走到 $u$ 对应的叶子。
而对于 $u$ 到 $\operatorname{lca}(u,v)$ 上面的所有重链（不包含 $\operatorname{lca}(u,v)$），这部分的复杂度是 $O(h)$ 的。
其中 $h$ 是 GBBT 的树高，根据上文可以得到为 $O(\log n)$。
根据上面的分析，得到一次前缀查询是从 $u$ 对应的叶子走到 $rt_u$ 的过程，而所有走过的路径在 GBBT 上面组成了一条从一个节点向根方向的链，长度不超过树的高度，所以是 $O(h)$ 的。
因此这一部分的时间复杂度是 $O(\log n)$。
$v$ 到 $\operatorname{lca}(u,v)$ 上面的所有重链同理。
$\operatorname{lca}(u,v)$ 的重链做一次区间查询，复杂度是 $O(\log len) \leq O(\log n)$ 的。
因此一次路径操作的时间复杂度是 $O(\log n)$。
### 拓展
#### 子树操作
在 GBBT 上进行子树操作是很复杂的，一般不建议用 GBBT 写同时有路径操作和子树操作的题。
但是理论上 GBBT 是可以同时维护简单的路径 / 子树操作的，例如树剖模板题。
可以阅读[文章](https://www.luogu.com.cn/article/tul5v12m)了解。
#### 可持久化
参考[该文章](https://www.luogu.com.cn/article/88v1dia4)。
### 习题
见[题单](https://www.luogu.com.cn/training/851940)，大部分路径操作题都可以拿来练手。
## GBBT 优化动态 DP
对于路径类 DDP 的实现，其实和维护路径信息是一样的，不再介绍。
对于子树类 DDP 的实现，其实是一个只有到根路径修改的特化，本质仍然和维护路径信息相同。
只有到根路径修改的情况下，可以直接使用迭代式的修改，使用 nodey 和 leafy 都很简单。
这里以 [P4751 【模板】动态 DP（加强版）](https://www.luogu.com.cn/problem/P4751) 为例。
如果你没有学过动态 DP，可以在我的[重链剖分学习笔记](https://www.luogu.com.cn/article/z62murs1)中了解。
建树部分和维护普通信息是一致的，因此只介绍修改部分。
这里给出 nodey-tree 和 leafy-tree 的实现。
::::info[nodey-tree]
```cpp
struct node {
int ls, rs, pr;//左右儿子和父节点
mat val, mul;//该节点的矩阵和 nodey-tree 的子树乘积
} t[N];
#define lc t[p].ls
#define rc t[p].rs
inline void up(int p){t[p].mul = rc || lc ? t[rc].mul * t[p].val * t[lc].mul : t[p].val;}//pushup需要计算节点本身的值和左右子树的值
//pushup 特判叶子节点可以减小常数
```
```cpp
inline void get(int & x, int & y, const mat & ma){
x = max(ma.a[0][0], ma.a[1][0]);
y = max(ma.a[0][1], ma.a[1][1]);
}//x,y 分别为初始状态矩阵与 ma 相乘结果矩阵 M 的 M[0][0] 和 M[0][1]
void updt(int u, int x){//这里记录父节点可以直接一直向上跳直到跳到全局的根，实现会简单很多
t[u].val.a[1][0] += x - a[u];//更新 u 的转移矩阵
a[u] = x;//更新 a[u]
while (u){
int p = t[u].pr; //p 为 u 在 GBBT 上的父亲
if (p && lc != u && rc != u){//向上跳了一条轻边，需要更新父节点的值
int f1, f0, nf1, nf0;
get(f1, f0, t[u].mul);//旧的贡献值
up(u);//更新 u
get(nf1, nf0, t[u].mul);//新的贡献值
int d0 = max(nf1, nf0) - max(f1, f0), d1 = nf0 - f0;
t[p].val.a[0][1] = t[p].val.a[1][1] += d0;
t[p].val.a[1][0] += d1;//更新 p 的转移矩阵
}
else up(u);//更新信息
u = p;
}
}
```
:::info[完整代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
int n, m;
int a[N];
vector<int> e[N];
int fa[N], sz[N], dep[N], son[N];
int f[N][2];
void dfs1(int u, int pr){
fa[u] = pr;
sz[u] = 1;
dep[u] = dep[pr] + 1;
f[u][1] = a[u];
for (int v : e[u]) if (v != pr){
dfs1(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}
}
struct mat {
int a[2][2];
};
const mat I = {{{0,-INF}, {-INF, 0}}};
//单位矩阵
const mat E = {{{-INF,-INF}, {-INF,-INF}}};
//空矩阵
const mat F0 = {{{0, 0}, {-INF,-INF}}};
//初始的转移矩阵
inline mat operator * (const mat & x, const mat & y){
return {{
{max(x.a[0][0] + y.a[0][0], x.a[0][1] + y.a[1][0]), max(x.a[0][0] + y.a[0][1], x.a[0][1] + y.a[1][1])},
{max(x.a[1][0] + y.a[0][0], x.a[1][1] + y.a[1][0]), max(x.a[1][0] + y.a[0][1], x.a[1][1] + y.a[1][1])}
}
};
}
//使用了矩乘展开以减小常数
struct node {
int ls, rs, pr;
//左右儿子和父节点
mat val, mul;
//该节点的矩阵和 nodey-tree 的子树乘积
} t[N];
#define lc t[p].ls
#define rc t[p].rs
inline void up(int p){t[p].mul = rc || lc ? t[rc].mul * t[p].val * t[lc].mul : t[p].val;}//pushup需要计算节点本身的值和左右子树的值
//pushup 特判叶子节点可以减小常数
int nod[N], cnt;
int build(int l, int r){
if (l > r) return 0;
int L = l, R = r;
while (L < R){
int mid = (L + R) >> 1;
if (2 * (sz[nod[l]] - sz[nod[mid + 1]]) < sz[nod[l]] - sz[nod[r + 1]]) L = mid + 1;
else R = mid;
}
int x = L, p = nod[x];
lc = build(l, x - 1), rc = build(x + 1, r);
if (lc) t[lc].pr = p;
if (rc) t[rc].pr = p;
up(p);
return p;
}
int dfs2(int u){//需要处理轻儿子对 dp 的贡献，这里直接在节点的矩阵上面修改
for (int x = u; x; x = son[x]) t[x].val.a[1][0] = a[x], t[x].val.a[0][0] =-INF;
for (int x = u; x; x = son[x]) for (int y : e[x]) if (y != fa[x] && y != son[x]){
t[dfs2(y)].pr = x;
t[x].val.a[0][1] = t[x].val.a[1][1] += max(f[y][0], f[y][1]);
t[x].val.a[1][0] += f[y][0];
}
cnt = 0;
for (int x = u; x; x = son[x]) nod[++cnt] = x;
nod[cnt + 1] = 0;
return build(1, cnt);
}
inline void get(int & x, int & y, const mat & ma){
x = max(ma.a[0][0], ma.a[1][0]);
y = max(ma.a[0][1], ma.a[1][1]);
}
//x,y 分别为初始状态矩阵与 ma 相乘结果矩阵 M 的 M[0][0] 和 M[0][1]
void updt(int u, int x){//这里记录父节点可以直接一直向上跳直到跳到全局的根，实现会简单很多
t[u].val.a[1][0] += x - a[u];
//更新 u 的转移矩阵
a[u] = x;
//更新 a[u]
while (u){
int p = t[u].pr;
//p 为 u 在 GBBT 上的父亲
if (p && lc != u && rc != u){//向上跳了一条轻边，需要更新父节点的值
int f1, f0, nf1, nf0;
get(f1, f0, t[u].mul); //旧的贡献值
up(u); //更新 u
get(nf1, nf0, t[u].mul); //新的贡献值
int d0 = max(nf1, nf0) - max(f1, f0), d1 = nf0 - f0;
t[p].val.a[0][1] = t[p].val.a[1][1] += d0;
t[p].val.a[1][0] += d1;
//更新 p 的转移矩阵
}
else up(u); //更新信息
u = p;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
rep(i, 1, n) cin >> a[i];
rep(i, 2, n){
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1, 0);
t[0].mul = I;
int rt = dfs2(1);
int ans = 0;
while (m--){
int u, x;
cin >> u >> x;
u ^= ans;
updt(u, x);
int f1, f0;
get(f1, f0, t[rt].mul);
ans = max(f1, f0);
cout << ans << '\n';
}
return 0;
}
```
:::
::::
::::info[leafy-tree]
```cpp
struct node {
int ls, rs, pr;//左右儿子和父节点
mat mul;//leafy-tree 的子树乘积
} t[N<<1];
int tot;// GBBT 的叶子编号为节点编号，新增节点编号由 tot 记录
#define lc t[p].ls
#define rc t[p].rs
inline mat getmat(int u){return {{{-INF, g[u][0]}, {g[u][1], g[u][0]}}};}
inline void up(int p){t[p].mul = rc || lc ? t[rc].mul * t[lc].mul : getmat(p);}//需要特判 p 是否为叶子
```
```cpp
inline void get(int & x, int & y, const mat & ma){
x = max(ma.a[0][0], ma.a[1][0]);
y = max(ma.a[0][1], ma.a[1][1]);
}//x,y 分别为初始状态矩阵与 ma 相乘结果矩阵 M 的 M[0][0] 和 M[0][1]，写这个函数是为了减少常数
void updt(int u, int x){//这里记录父节点可以直接一直向上跳直到跳到全局的根，实现会简单很多
g[u][1] += x - a[u];//更新 u 的转移矩阵
a[u] = x;//更新 a[u]
while (u){
int p = t[u].pr;//p 为 u 在 GBBT 上的父亲
if (p && lc != u && rc != u){//向上跳了一条轻边，需要更新父节点的值
int f1, f0, nf1, nf0;
get(f1, f0, t[u].mul);//旧的贡献值
up(u);//更新 u
get(nf1, nf0, t[u].mul);//新的贡献值
g[p][0] += max(nf1, nf0) - max(f1, f0), g[p][1] += nf0 - f0;//更新 p 的转移矩阵
}
else up(u);//更新信息
u = p;
}
}
```
:::info[完整代码]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 1e6 + 5, INF = 0x3f3f3f3f;
int n, m;
int a[N];
vector<int> e[N];
int fa[N], sz[N], dep[N], son[N];
int f[N][2], g[N][2];
void dfs1(int u, int pr){
fa[u] = pr;
sz[u] = 1;
dep[u] = dep[pr] + 1;
f[u][1] = a[u];
for (int v : e[u]) if (v != pr){
dfs1(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}
}
struct mat {
int a[2][2];
};
const mat I = {{{0,-INF}, {-INF, 0}}};
//单位矩阵
const mat E = {{{-INF,-INF}, {-INF,-INF}}};
//空矩阵
const mat F0 = {{{0, 0}, {-INF,-INF}}};
//初始的转移矩阵
inline mat operator * (const mat & x, const mat & y){
return {{
{max(x.a[0][0] + y.a[0][0], x.a[0][1] + y.a[1][0]), max(x.a[0][0] + y.a[0][1], x.a[0][1] + y.a[1][1])},
{max(x.a[1][0] + y.a[0][0], x.a[1][1] + y.a[1][0]), max(x.a[1][0] + y.a[0][1], x.a[1][1] + y.a[1][1])}
}
};
}
//使用了矩乘展开以减小常数
struct node {
int ls, rs, pr;
//左右儿子和父节点
mat mul;
//leafy-tree 的子树乘积
} t[N<<1];
int tot;
// GBBT 的叶子编号为节点编号，新增节点编号由 tot 记录
#define lc t[p].ls
#define rc t[p].rs
inline mat getmat(int u){return {{{-INF, g[u][0]}, {g[u][1], g[u][0]}}};}
inline void up(int p){t[p].mul = rc || lc ? t[rc].mul * t[lc].mul : getmat(p);}//需要特判 p 是否为叶子
int nod[N], cnt;
int build(int l, int r){
if (l == r){
int p = nod[l];
t[p].mul = getmat(p);
return p;
}
int L = l, R = r;
while (L < R){
int mid = (L + R) >> 1;
if (2 * (sz[nod[l]] - sz[nod[mid + 1]]) < sz[nod[l]] - sz[nod[r + 1]]) L = mid + 1;
else R = mid;
}
if (L == r)--L;
int x = L, p = ++tot;
lc = build(l, x), rc = build(x + 1, r);
if (lc) t[lc].pr = p;
if (rc) t[rc].pr = p;
up(p);
return p;
}
int dfs2(int u){
for (int x = u; x; x = son[x]) g[x][1] = a[x];
for (int x = u; x; x = son[x]) for (int y : e[x]) if (y != fa[x] && y != son[x]){
t[dfs2(y)].pr = x;
g[x][0] += max(f[y][0], f[y][1]);
g[x][1] += f[y][0];
}
cnt = 0;
for (int x = u; x; x = son[x]) nod[++cnt] = x;
nod[cnt + 1] = 0;
return build(1, cnt);
}
inline void get(int & x, int & y, const mat & ma){
x = max(ma.a[0][0], ma.a[1][0]);
y = max(ma.a[0][1], ma.a[1][1]);
}
//x,y 分别为初始状态矩阵与 ma 相乘结果矩阵 M 的 M[0][0] 和 M[0][1]，写这个函数是为了减少常数
void updt(int u, int x){//这里记录父节点可以直接一直向上跳直到跳到全局的根，实现会简单很多
g[u][1] += x - a[u];
//更新 u 的转移矩阵
a[u] = x;
//更新 a[u]
while (u){
int p = t[u].pr;
//p 为 u 在 GBBT 上的父亲
if (p && lc != u && rc != u){//向上跳了一条轻边，需要更新父节点的值
int f1, f0, nf1, nf0;
get(f1, f0, t[u].mul); //旧的贡献值
up(u); //更新 u
get(nf1, nf0, t[u].mul); //新的贡献值
g[p][0] += max(nf1, nf0) - max(f1, f0), g[p][1] += nf0 - f0; //更新 p 的转移矩阵
}
else up(u); //更新信息
u = p;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
rep(i, 1, n) cin >> a[i];
rep(i, 2, n){
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1, 0);
t[0].mul = I;
tot = n;
int rt = dfs2(1);
int ans = 0;
while (m--){
int u, x;
cin >> u >> x;
u ^= ans;
updt(u, x);
int f1, f0;
get(f1, f0, t[rt].mul);
ans = max(f1, f0);
cout << ans << '\n';
}
return 0;
}
```
:::
::::
可以发现，实现都很简单，但是 nodey-tree 更加简洁。
并且从评测结果来看，[nodey-tree](https://www.luogu.com.cn/record/300764995) 的时空常数都比 [leafy-tree](https://www.luogu.com.cn/record/300764021) 小（也有可能是我的实现问题），所以 nodey-tree 是比较推荐的写法。
根据代码很容易分析，单次修改的复杂度是 $O(h)=O(\log n)$ 的。
### 习题
见[题单](https://www.luogu.com.cn/training/1007000)。
### 附录：性能对比
下面是本地的测试结果对比。
使用的是 DDP 数据加强版，为了方便去掉了强制在线，但是代码都是在线的。
为了体现常数和复杂度差异，测试数据为 $n=4 \times 10^6$，$m=10^7$。
树的结构是完全二叉树套链。
:::info[Gen]
```cpp
#include<bits/stdc++.h>
#include <chrono>
using namespace std;
#define ll long long
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
struct io {
#define ll long long
#define lll __int128
#define SZ 1<<21
char buf[SZ],*p1,*p2;
char pbuf[SZ],*pp;
io() : p1(buf), p2(buf), pp(pbuf){}
~io(){fwrite(pbuf, 1, pp - pbuf, stdout);}
inline char gc(){
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, SZ, stdin);
return p1 == p2 ? EOF :*p1++;
}
#define isdigit(ch) (ch>47&&ch<58)
inline io & operator >>(int & x){
x = 0;
bool neg = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc()) if (ch == '-') neg = 1;
if (neg) for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) - (ch ^ 48);
else for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + (ch ^ 48);
return * this;
}
inline io & operator >>(ll & x){
x = 0;
bool neg = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc()) if (ch == '-') neg = 1;
if (neg) for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) - (ch ^ 48);
else for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + (ch ^ 48);
return * this;
}
inline io & operator >>(lll & x){
x = 0;
bool neg = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc()) if (ch == '-') neg = 1;
if (neg) for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) - (ch ^ 48);
else for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + (ch ^ 48);
return * this;
}
inline io & operator >>(char & c){
c = gc();
for (; isspace(c);) c = gc();
return * this;
}
inline io & operator >>(string & s){
s = "";
char c = gc();
for (; isspace(c);) c = gc();
for (; !isspace(c) && c != EOF; c = gc()) s += c;
return * this;
}
inline void push(const char & c){
if (pp - pbuf == SZ) fwrite(pbuf, 1, SZ, stdout), pp = pbuf;
*pp++ = c;
}
int stk[45], top;
inline io & operator << (int x){
if (!x){push('0'); return * this;}
if (x < 0){push('-'); x =-x;}
while (x) stk[++top] = x % 10, x /= 10;
while (top) push(stk[top--] ^ 48);
return * this;
}
inline io & operator << (ll x){
if (!x){push('0'); return * this;}
if (x < 0){push('-'); x =-x;}
while (x) stk[++top] = x % 10, x /= 10;
while (top) push(stk[top--] ^ 48);
return * this;
}
inline io & operator << (lll x){
if (!x){push('0'); return * this;}
if (x < 0){push('-'); x =-x;}
while (x) stk[++top] = x % 10, x /= 10;
while (top) push(stk[top--] ^ 48);
return * this;
}
inline io & operator << (const char & c){
push(c);
return * this;
}
inline io & operator << (const string & s){
for (char c : s) push(c);
return * this;
}
} IO;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r){
return rng() % (r - l + 1) + l;
}
const int N = 4e6, M = 1e7;
int n = N, m = M;
#define linkfa(i) (((i)-1)*2000+1)
int main(){
freopen("DDP.in", "w", stdout);
IO << n << ' ' << m << '\n';
rep(u, 1, n) IO << rnd(-100, 100) << " \n"[u == n];
rep(i, 1, 2000){
if (i != 1) IO << linkfa(i) << ' ' << linkfa(i >> 1) + 1999 << '\n';
rep(j, 1, 1999) IO << linkfa(i) + j - 1 << ' ' << linkfa(i) + j << '\n';
}
rep(i, 1, m){
int u = linkfa(rnd(1025, 2000)) + rnd(1000, 1999), x = rnd(-100, 100);
IO << u << ' ' << x << '\n';
}
return 0;
}
```
:::
每一个代码测试三次，运行用时和峰值内存可供参考。
Nodey-tree：
5042.774 ms/447896 KB
5005.918 ms/447900 KB
5022.028 ms/447896 KB
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
struct io {
#define SZ 1<<21
char buf[SZ], pbuf[SZ];
char * p1,*p2,*pp;
io() : p1(buf), p2(buf), pp(pbuf){}
~io(){fwrite(pbuf, 1, pp - pbuf, stdout);}
inline char gc(){
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, SZ, stdin);
return p1 == p2 ? EOF :*p1++;
}
#define isdigit(ch) (ch>47&&ch<58)
template<typename T>inline io & operator >>(T & x){
x = 0;
bool neg = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc()) if (ch == '-') neg = 1;
if (neg) for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) - (ch ^ 48);
else for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + (ch ^ 48);
return * this;
}
inline void push(const char & c){
if (pp - pbuf == SZ) fwrite(pbuf, 1, SZ, stdout), pp = pbuf;
*pp++ = c;
}
int stk[45], top;
template<typename T>inline io & operator << (T x){
if (!x){push('0'); push('\n'); return * this;}
if (x < 0){push('-'); x =-x;}
while (x) stk[++top] = x % 10, x /= 10;
while (top) push(stk[top--] ^ 48);
push('\n');
return * this;
}
} IO;
const int N = 4e6 + 5, INF = 0x3f3f3f3f;
int n, m;
int a[N];
vector<int> e[N];
int fa[N], sz[N], dep[N], son[N];
int f[N][2];
void dfs1(int u, int pr){
fa[u] = pr;
sz[u] = 1;
dep[u] = dep[pr] + 1;
f[u][1] = a[u];
for (int v : e[u]) if (v != pr){
dfs1(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}
}
struct mat {
int a[2][2];
};
const mat I = {{{0,-INF}, {-INF, 0}}};
//单位矩阵
const mat E = {{{-INF,-INF}, {-INF,-INF}}};
//空矩阵
const mat F0 = {{{0, 0}, {-INF,-INF}}};
//初始的转移矩阵
inline mat operator * (const mat & x, const mat & y){
return {{
{max(x.a[0][0] + y.a[0][0], x.a[0][1] + y.a[1][0]), max(x.a[0][0] + y.a[0][1], x.a[0][1] + y.a[1][1])},
{max(x.a[1][0] + y.a[0][0], x.a[1][1] + y.a[1][0]), max(x.a[1][0] + y.a[0][1], x.a[1][1] + y.a[1][1])}
}
};
}
//使用了矩乘展开以减小常数
struct node {
int ls, rs, pr;
//左右儿子和父节点
mat val, mul;
//该节点的矩阵和 nodey-tree 的子树乘积
} t[N];
#define lc t[p].ls
#define rc t[p].rs
inline void up(int p){t[p].mul = rc || lc ? t[rc].mul * t[p].val * t[lc].mul : t[p].val;}//pushup需要计算节点本身的值和左右子树的值
//pushup 特判叶子节点可以减小常数
int nod[N], cnt;
int build(int l, int r){
if (l > r) return 0;
int L = l, R = r;
while (L < R){
int mid = (L + R) >> 1;
if (2 * (sz[nod[l]] - sz[nod[mid + 1]]) < sz[nod[l]] - sz[nod[r + 1]]) L = mid + 1;
else R = mid;
}
int x = L, p = nod[x];
lc = build(l, x - 1), rc = build(x + 1, r);
if (lc) t[lc].pr = p;
if (rc) t[rc].pr = p;
up(p);
return p;
}
int dfs2(int u){//需要处理轻儿子对 dp 的贡献，这里直接在节点的矩阵上面修改
for (int x = u; x; x = son[x]) t[x].val.a[1][0] = a[x], t[x].val.a[0][0] =-INF;
for (int x = u; x; x = son[x]) for (int y : e[x]) if (y != fa[x] && y != son[x]){
t[dfs2(y)].pr = x;
t[x].val.a[0][1] = t[x].val.a[1][1] += max(f[y][0], f[y][1]);
t[x].val.a[1][0] += f[y][0];
}
cnt = 0;
for (int x = u; x; x = son[x]) nod[++cnt] = x;
nod[cnt + 1] = 0;
return build(1, cnt);
}
inline void get(int & x, int & y, const mat & ma){
x = max(ma.a[0][0], ma.a[1][0]);
y = max(ma.a[0][1], ma.a[1][1]);
}
//x,y 分别为初始状态矩阵与 ma 相乘结果矩阵 M 的 M[0][0] 和 M[0][1]
void updt(int u, int x){//这里记录父节点可以直接一直向上跳直到跳到全局的根，实现会简单很多
t[u].val.a[1][0] += x - a[u];
//更新 u 的转移矩阵
a[u] = x;
//更新 a[u]
while (u){
int p = t[u].pr;
//p 为 u 在 GBBT 上的父亲
if (p && lc != u && rc != u){//向上跳了一条轻边，需要更新父节点的值
int f1, f0, nf1, nf0;
get(f1, f0, t[u].mul); //旧的贡献值
up(u); //更新 u
get(nf1, nf0, t[u].mul); //新的贡献值
int d0 = max(nf1, nf0) - max(f1, f0), d1 = nf0 - f0;
t[p].val.a[0][1] = t[p].val.a[1][1] += d0;
t[p].val.a[1][0] += d1;
//更新 p 的转移矩阵
}
else up(u); //更新信息
u = p;
}
}
int main(){
freopen("DDP.in", "r", stdin);
freopen("DDP.out", "w", stdout);
IO >> n >> m;
rep(i, 1, n) IO >> a[i];
rep(i, 2, n){
int u, v;
IO >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1, 0);
t[0].mul = I;
int rt = dfs2(1);
int ans = 0;
while (m--){
int u, x;
IO >> u >> x;
//u ^= ans;
updt(u, x);
int f1, f0;
get(f1, f0, t[rt].mul);
ans = max(f1, f0);
IO << ans;
}
return 0;
}
```
:::
Leafy-tree：
6094.566 ms/541804 KB
6172.198 ms/526000 KB
6044.554 ms/526004 KB
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
struct io {
#define SZ 1<<21
char buf[SZ], pbuf[SZ];
char * p1,*p2,*pp;
io() : p1(buf), p2(buf), pp(pbuf){}
~io(){fwrite(pbuf, 1, pp - pbuf, stdout);}
inline char gc(){
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, SZ, stdin);
return p1 == p2 ? EOF :*p1++;
}
#define isdigit(ch) (ch>47&&ch<58)
template<typename T>inline io & operator >>(T & x){
x = 0;
bool neg = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc()) if (ch == '-') neg = 1;
if (neg) for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) - (ch ^ 48);
else for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + (ch ^ 48);
return * this;
}
inline void push(const char & c){
if (pp - pbuf == SZ) fwrite(pbuf, 1, SZ, stdout), pp = pbuf;
*pp++ = c;
}
int stk[45], top;
template<typename T>inline io & operator << (T x){
if (!x){push('0'); push('\n'); return * this;}
if (x < 0){push('-'); x =-x;}
while (x) stk[++top] = x % 10, x /= 10;
while (top) push(stk[top--] ^ 48);
push('\n');
return * this;
}
} IO;
const int N = 4e6 + 5, INF = 0x3f3f3f3f;
int n, m;
int a[N];
vector<int> e[N];
int fa[N], sz[N], dep[N], son[N];
int f[N][2], g[N][2];
void dfs1(int u, int pr){
fa[u] = pr;
sz[u] = 1;
dep[u] = dep[pr] + 1;
f[u][1] = a[u];
for (int v : e[u]) if (v != pr){
dfs1(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}
}
struct mat {
int a[2][2];
};
const mat I = {{{0,-INF}, {-INF, 0}}};
//单位矩阵
const mat E = {{{-INF,-INF}, {-INF,-INF}}};
//空矩阵
const mat F0 = {{{0, 0}, {-INF,-INF}}};
//初始的转移矩阵
inline mat operator * (const mat & x, const mat & y){
return {{
{max(x.a[0][0] + y.a[0][0], x.a[0][1] + y.a[1][0]), max(x.a[0][0] + y.a[0][1], x.a[0][1] + y.a[1][1])},
{max(x.a[1][0] + y.a[0][0], x.a[1][1] + y.a[1][0]), max(x.a[1][0] + y.a[0][1], x.a[1][1] + y.a[1][1])}
}
};
}
//使用了矩乘展开以减小常数
struct node {
int ls, rs, pr;
//左右儿子和父节点
mat mul;
//leafy-tree 的子树乘积
} t[N<<1];
int tot;
// GBBT 的叶子编号为节点编号，新增节点编号由 tot 记录
#define lc t[p].ls
#define rc t[p].rs
inline mat getmat(int u){return {{{-INF, g[u][0]}, {g[u][1], g[u][0]}}};}
inline void up(int p){t[p].mul = rc || lc ? t[rc].mul * t[lc].mul : getmat(p);}//需要特判 p 是否为叶子
int nod[N], cnt;
int build(int l, int r){
if (l == r){
int p = nod[l];
t[p].mul = getmat(p);
return p;
}
int L = l, R = r;
while (L < R){
int mid = (L + R) >> 1;
if (2 * (sz[nod[l]] - sz[nod[mid + 1]]) < sz[nod[l]] - sz[nod[r + 1]]) L = mid + 1;
else R = mid;
}
if (L == r)--L;
int x = L, p = ++tot;
lc = build(l, x), rc = build(x + 1, r);
if (lc) t[lc].pr = p;
if (rc) t[rc].pr = p;
up(p);
return p;
}
int dfs2(int u){
for (int x = u; x; x = son[x]) g[x][1] = a[x];
for (int x = u; x; x = son[x]) for (int y : e[x]) if (y != fa[x] && y != son[x]){
t[dfs2(y)].pr = x;
g[x][0] += max(f[y][0], f[y][1]);
g[x][1] += f[y][0];
}
cnt = 0;
for (int x = u; x; x = son[x]) nod[++cnt] = x;
nod[cnt + 1] = 0;
return build(1, cnt);
}
inline void get(int & x, int & y, const mat & ma){
x = max(ma.a[0][0], ma.a[1][0]);
y = max(ma.a[0][1], ma.a[1][1]);
}
//x,y 分别为初始状态矩阵与 ma 相乘结果矩阵 M 的 M[0][0] 和 M[0][1]，写这个函数是为了减少常数
void updt(int u, int x){//这里记录父节点可以直接一直向上跳直到跳到全局的根，实现会简单很多
g[u][1] += x - a[u];
//更新 u 的转移矩阵
a[u] = x;
//更新 a[u]
while (u){
int p = t[u].pr;
//p 为 u 在 GBBT 上的父亲
if (p && lc != u && rc != u){//向上跳了一条轻边，需要更新父节点的值
int f1, f0, nf1, nf0;
get(f1, f0, t[u].mul); //旧的贡献值
up(u); //更新 u
get(nf1, nf0, t[u].mul); //新的贡献值
g[p][0] += max(nf1, nf0) - max(f1, f0), g[p][1] += nf0 - f0; //更新 p 的转移矩阵
}
else up(u); //更新信息
u = p;
}
}
int getht(int u){
int h = 0;
for (; u; u = t[u].pr)++h;
return h;
}
int main(){
freopen("DDP.in", "r", stdin);
freopen("DDP.out", "w", stdout);
IO >> n >> m;
rep(i, 1, n) IO >> a[i];
rep(i, 2, n){
int u, v;
IO >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1, 0);
t[0].mul = I;
tot = n;
int rt = dfs2(1);
int ans = 0;
while (m--){
int u, x;
IO >> u >> x;
//u ^= ans;
updt(u, x);
int f1, f0;
get(f1, f0, t[rt].mul);
ans = max(f1, f0);
IO << ans;
}
return 0;
}
```
:::
树剖线段树：
12190.496 ms/561196 KB
11667.443 ms/561196 KB
12140.327 ms/561196 KB
:::info[Code]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
const int N = 4e6 + 5, INF = 0x3f3f3f3f;
struct io {
#define SZ 1<<21
char buf[SZ], pbuf[SZ];
char * p1,*p2,*pp;
io() : p1(buf), p2(buf), pp(pbuf){}
~io(){fwrite(pbuf, 1, pp - pbuf, stdout);}
inline char gc(){
if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, SZ, stdin);
return p1 == p2 ? EOF :*p1++;
}
#define isdigit(ch) (ch>47&&ch<58)
template<typename T>inline io & operator >>(T & x){
x = 0;
bool neg = 0;
char ch = gc();
for (; !isdigit(ch); ch = gc()) if (ch == '-') neg = 1;
if (neg) for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) - (ch ^ 48);
else for (; isdigit(ch); ch = gc()) x = (x << 1) + (x << 3) + (ch ^ 48);
return * this;
}
inline void push(const char & c){
if (pp - pbuf == SZ) fwrite(pbuf, 1, SZ, stdout), pp = pbuf;
*pp++ = c;
}
int stk[45], top;
template<typename T>inline io & operator << (T x){
if (!x){push('0'); push('\n'); return * this;}
if (x < 0){push('-'); x =-x;}
while (x) stk[++top] = x % 10, x /= 10;
while (top) push(stk[top--] ^ 48);
push('\n');
return * this;
}
} IO;
int n, m;
int a[N];
vector<int> e[N];
int fa[N], sz[N], dep[N], son[N];
int f[N][2], g[N][2];
void dfs1(int u, int pr){
fa[u] = pr;
sz[u] = 1;
dep[u] = dep[pr] + 1;
f[u][1] = a[u];
for (int v : e[u]) if (v != pr){
dfs1(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
f[u][1] += f[v][0];
f[u][0] += max(f[v][0], f[v][1]);
}
}
int top[N], bot[N], dfn[N], nod[N], cnt;
struct mat {
int a[2][2];
};
const mat I = {{{0,-INF}, {-INF, 0}}};
const mat E = {{{-INF,-INF}, {-INF,-INF}}};
const mat F0 = {{{0, 0}, {-INF,-INF}}};
mat operator * (const mat & x, const mat & y){
return {{
{max(x.a[0][0] + y.a[0][0], x.a[0][1] + y.a[1][0]), max(x.a[0][0] + y.a[0][1], x.a[0][1] + y.a[1][1])},
{max(x.a[1][0] + y.a[0][0], x.a[1][1] + y.a[1][0]), max(x.a[1][0] + y.a[0][1], x.a[1][1] + y.a[1][1])}
}
};
}
struct node {
mat mul;
int lson, rson;
} t[N<<2];
int rt[N], ct;
#define ls t[p].lson
#define rs t[p].rson
#define mid ((pl+pr)>>1)
mat getmat(int u){return {{{-INF, g[u][0]}, {g[u][1], g[u][0]}}};}
void up(int p){t[p].mul = t[rs].mul * t[ls].mul;}
void build(int & p, int pl, int pr){
p = ++ct;
if (pl == pr){
t[p].mul = getmat(nod[pl]);
return;
}
build(ls, pl, mid);
build(rs, mid + 1, pr);
up(p);
}
void dfs2(int u, int tp){
top[u] = tp;
bot[u] = u;
dfn[u] = ++cnt;
nod[cnt] = u;
g[u][1] = a[u];
if (!son[u]) return;
dfs2(son[u], tp);
bot[u] = bot[son[u]];
for (int v : e[u]) if (v != fa[u] && v != son[u]){
dfs2(v, v);
g[u][0] += max(f[v][0], f[v][1]);
g[u][1] += f[v][0];
}
}
int stk[20], st;
void upd(int u){
int p = rt[top[u]], pl = dfn[top[u]], pr = dfn[bot[u]], x = dfn[u];
while (pl != pr){
stk[++st] = p;
x <= mid ? (pr = mid, p = ls) : (pl = mid + 1, p = rs);
}
t[p].mul = getmat(u);
while (st) up(stk[st--]);
}
void updt(int u, int x){
g[u][1] += x - a[u];
a[u] = x;
while (u){
int tp = top[u], p = fa[tp];
mat F = F0 * t[rt[tp]].mul;
int f1 = F.a[0][0], f0 = F.a[0][1];
upd(u);
mat nF = F0 * t[rt[tp]].mul;
int nf1 = nF.a[0][0], nf0 = nF.a[0][1];
if (p) g[p][0] += max(nf1, nf0) - max(f1, f0), g[p][1] += nf0 - f0;
u = p;
}
}
int main(){
freopen("DDP.in", "r", stdin);
freopen("DDP.out", "w", stdout);
IO >> n >> m;
rep(i, 1, n) IO >> a[i];
rep(i, 2, n){
int u, v;
IO >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1, 0);
dfs2(1, 1);
rep(u, 1, n) if (top[u] == u) build(rt[u], dfn[u], dfn[bot[u]]);
while (m--){
int u, x;
IO >> u >> x;
updt(u, x);
mat res = F0 * t[rt[1]].mul;
IO << max(res.a[0][0], res.a[0][1]);
}
return 0;
}
```
:::
以下为我的设备配置和编译选项：
处理器：
AMD Ryzen 7 5800X3D 8-Core Processor 3.40 GHz
机带RAM：
32.0 GB
速度：2400 MHz
编译器：
mingw gcc 15.1.0 (posix-seh-ucrt)
Version: 15.1.0
Platform: Windows
编译选项：
`-std=c++17 -O2 -static -Wl,--stack=1000000000 -Wshadow`
可以看出来两种 GBBT 的和树剖线段树的常数差距和复杂度优化。
upd on 2026/10/6：
原来的 `Gen.cpp` 写错了，数据不够强没卡满树剖，已更新。