警示后人：
- 很多数据结构的根（包括GBBT）的根都不是 。
- 请看清楚你的矩阵乘法到底在做什么。一般地，转移式中向量左乘矩阵的
pushup是深-中-浅（右中左），右乘矩阵的是左中右。 - 写一个函数从矩阵中提取 时，务必注意。
- 关于DDP的还原问题（保卫王国）：请注意还原的后效性，即更改 后还原顺序应该是 （这里 是任意点）
引入 CF1814E
有一条长度为 的无向链。对于 ，节点 和节点 之间有一条权值为 的无向边。
有 次询问，每次修改一个边权（有后效），然后询问：
- 假设有 辆车，初始时第 辆车停在节点 。你需要移动这些车，使得每辆车都不在自己原来的节点，且每个节点都恰有一辆车。求所有车移动经过的边的权值之和的最小值。
。
考虑不带修改的情况下，一种直接的想法是将一段 循环移位到 ，这样做是 。这样做是正确的。问题转化为了 个数中选择若干个数，使得相邻两个数必须选一个，最小化选的数的和。
为第 个数选/不选的最小代价。
写成矩阵乘法就是
\begin{bmatrix} f_{i,0} \\ f_{i,1} \end{bmatrix} =\begin{bmatrix} \infty & 0 \\ w_i & w_i \end{bmatrix} \begin{bmatrix} f_{i-1,0} \\ f_{i-1,1} \end{bmatrix}$$ 注意这里是广义 $(\min, +)$ 矩阵乘法，$(AB)_{ij} = \min_k \{A_{ik} + B_{kj}\}$。 用线段树维护$\begin{bmatrix} \infty & 0 \\ w_i & w_i \end{bmatrix}$的乘积，支持单点修改即可。 ## [P4719](https://www.luogu.com.cn/problem/P4719) 【模板】动态 DP 给定一棵 $n$ 个点的树，点带点权。 有 $m$ 次操作，每次操作给定 $x,y$，表示修改点 $x$ 的权值为 $y$。 你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 $1\le n,m\le 10^5$，$1 \leq u, v , x \leq n$，$-10^2 \leq a_i, y \leq 10^2$。 一般的最大权独立集式子: $$f_{u,0}=\sum \limits_v \max(f_{v,0},f_{v,1})\\ f_{u,1}=w_u+\sum \limits_v f_{v,0}$$ $f_{u,0/1}$ 是 $u$ 不选/可以选的答案。 对整棵树进行树剖，分别记重儿子和轻儿子的答案。我们定义一个辅助数组 $g_{u,0/1}$ 代表 $u$ 的所有轻儿子全不选/可以选的贡献（包括 $w_u$）。于是有（$v$ 是 $u$ 的重儿子） $$f_{u,0}=f_{v,1}+g_{u,1}\\f_{u,1}=\max(f_{v,0}+g_{u,0},f_{u,0})$$ - 这里为什么要把 $g$ 定义为这么奇怪的形式？ 我理解的是，为了能将重链从树中剥离开单独进行矩阵加速，必须将汇入重链的信息和沿重链传递的信息剥离开。 根据转移式，有 $$\begin{bmatrix}f_{u,0}& f_{u,1}\end{bmatrix}=\begin{bmatrix}f_{v,0}& f_{v,1}\end{bmatrix} \times \begin{bmatrix}-\infty& g_{u,0}\\ g_{u,1} & g_{u,1}\end{bmatrix}$$ （这里是 $(\max,+)$ 矩阵乘法） 然后重链剖分，拿线段树维护这一堆矩阵。修改节点时，只需要修改其 $g_u$ 矩阵，然后跑到重链的最顶端，求出新的矩阵，对链顶父亲的 $g_u$ 修改一下，如此重复即可。由树剖可知，复杂度为 $O(n \log^2 n)$。 注意每条重链的链尾都是叶子节点，且只有叶子节点没有重儿子，所以这样 DP 和修改是对的。 ## 全局平衡二叉树 这个东西叫法很多，比如 Global Biased Tree,GBT(lxl)，Global Balanced Binary Tree,GBBT。姑且就叫 GBBT 吧。 考虑数据加强版 [P4751](https://www.luogu.com.cn/problem/P4751)，已经不允许双 $\log$ 了。记： $$\mathrm{Lsize}(u)=1+\sum \limits_{x\in \mathrm{LightSon}(u)} \mathrm{size}_x$$ 此时，如果在每一条重链上以 $\mathrm{Lsize}$ 为权值，找到加权后的中点，左右递归建树维护信息，均摊复杂度是 $O(\log n)$ 的。（每条重链的根向着原树内的父亲建一条虚边） ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; struct matrix{ int a[2][2]; matrix(){a[0][0]=a[0][1]=a[1][0]=a[1][1]=-1e9;} int* operator[](int x){return a[x];} matrix operator*(matrix &A)const{ matrix ret; for(int i=0;i<2;i++){ for(int k=0;k<2;k++){ for(int j=0;j<2;j++){ ret[i][j]=max(ret[i][j],a[i][k]+A[k][j]); } } } return ret; } }; struct node{ int l,r,fa; int lsize; matrix val,sum; //当前节点的g矩阵和维护的区间的矩阵乘积 }t[N]; int f(int x,int k){ return max(t[x].sum[1^k][0],t[x].sum[1^k][1]); } struct edge{int to,nxt;}es[N<<1]; int ecnt,head[N]; void addedge(int u,int v){es[++ecnt].nxt=head[u];es[ecnt].to=v;head[u]=ecnt;} int w[N]; int siz[N],faa[N],hson[N]; void dfs1(int now,int f){ siz[now]=1;faa[now]=f; for(int i=head[now];i;i=es[i].nxt){ int v=es[i].to; if(v==f)continue; dfs1(v,now); siz[now]+=siz[v]; if(siz[v]>siz[hson[now]])hson[now]=v; } t[now].lsize=siz[now]-siz[hson[now]]; } #define ls t[p].l #define rs t[p].r void pushup(int p){ t[p].sum=t[p].val; if(ls)t[p].sum=t[ls].sum*t[p].sum; if(rs)t[p].sum=t[p].sum*t[rs].sum; } int buildpart(int l,int r,vector<int> &vec){ if(l>r)return 0; int totl=0,pos=0,p=0; for(int i=l;i<=r;i++)totl+=t[vec[i]].lsize; for(int i=l;i<=r;i++){ totl-=2*t[vec[i]].lsize; if(totl<=0){pos=i;break;} } p=vec[pos]; ls=buildpart(l,pos-1,vec); rs=buildpart(pos+1,r,vec); if(ls)t[ls].fa=p; if(rs)t[rs].fa=p; pushup(p); return p; } int build(int now){ vector<int> vec; for(int p=now;p;p=hson[p]){ vec.push_back(p); t[p].val[0][0]=-1e9; t[p].val[0][1]=w[p]; t[p].val[1][0]=0; for(int i=head[p];i;i=es[i].nxt){ int v=es[i].to; if(v==faa[p]||v==hson[p])continue; int rt=build(v); t[rt].fa=p; t[p].val[0][1]+=f(rt,0); t[p].val[1][0]+=max(f(rt,0),f(rt,1)); } t[p].val[1][1]=t[p].val[1][0]; } return buildpart(0,vec.size()-1,vec); } bool isroot(int p){ return !t[p].fa or (t[t[p].fa].l!=p and t[t[p].fa].r!=p); } void modify(int p,int k){ t[p].val[0][1]+=(k-w[p]); w[p]=k; for(int now=p;now;now=t[now].fa){ if(isroot(now) and t[now].fa){ int fa=t[now].fa; int f0=f(now,0),f1=f(now,1); pushup(now); t[fa].val[0][1]+=f(now,0)-f0; t[fa].val[1][1]+=max(f(now,0),f(now,1))-max(f0,f1); t[fa].val[1][0]=t[fa].val[1][1]; } else pushup(now); } } int n,m; signed main(){ cin.tie(0)->sync_with_stdio(0); cin>>n>>m; for(int i=1;i<=n;i++)cin>>w[i]; int u,v; for(int i=1;i<n;i++){ cin>>u>>v; addedge(u,v); addedge(v,u); } dfs1(1,0); int root=build(1); int x,y,lstans=0; while(m--){ cin>>x>>y; x^=lstans; modify(x,y); lstans=max(f(root,0),f(root,1)); cout<<lstans<<'\n'; } return 0; } ``` ## 例题 ### [P5024 [NOIP 2018 提高组] 保卫王国](https://www.luogu.com.cn/problem/P5024) 模板是最大独立集，此题是最小覆盖集，并且要求 $1/2$ 个点必须选/必须不选。 $f_{u,0/1}$ 代表 $u$ 这个点可以不选/必须选，$g_{u,0/1}$ 代表 $u$ 的轻儿子全都选/可以不都选（包括 $u$ 自身花费）的最小代价。 $$\begin{bmatrix}f_{u,0}& f_{u,1}\end{bmatrix}=\begin{bmatrix}f_{v,0}& f_{v,1}\end{bmatrix} \begin{bmatrix}+\infty& g_{u,1} \\ g_{u,0} & g_{u,1}\end{bmatrix}$$ 这里是 $(\min,+)$ 矩阵乘法，直接维护即可。 对于【必须选/必须不选】的条件，考虑直接修改其 $f$。具体地，若必须选，则 $f_{u,0}=+\infty$，若必须不选，则 $f_{u,1}=+\infty$。实现上，直接把计算 $f_{u,0/1}$ 的那一列设为 $+\infty$。