DDP学习笔记&P4751题解

警示后人：

很多数据结构的根（包括GBBT）的根都不是 $1$ 。
请看清楚你的矩阵乘法到底在做什么。一般地，转移式中向量左乘矩阵的 pushup 是深-中-浅（右中左），右乘矩阵的是左中右。
写一个函数从矩阵中提取 $f$ 时，务必注意。
关于DDP的还原问题（保卫王国）：请注意还原的后效性，即更改 $u,v$ 后还原顺序应该是 $v,u$ （这里 $u,v$ 是任意点）

引入 CF1814E

有一条长度为 $n$ 的无向链。对于 $i = 1, 2, \cdots, n-1$ ，节点 $i$ 和节点 $i+1$ 之间有一条权值为 $w_i$ 的无向边。

有 $q$ 次询问，每次修改一个边权（有后效），然后询问：

假设有 $n$ 辆车，初始时第 $i$ 辆车停在节点 $i_0$ 。你需要移动这些车，使得每辆车都不在自己原来的节点，且每个节点都恰有一辆车。求所有车移动经过的边的权值之和的最小值。

$n, q \leq 2 \times 10^5,1 \leq w_i \leq 10^9$ 。

考虑不带修改的情况下，一种直接的想法是将一段 $a_i,\cdots,a_i+k$ 循环移位到 $a_{i+1},\cdots,a_{i+k},a_i$ ，这样做是 $2(w_i+\cdots w_{i+k-1})$ 。这样做是正确的。问题转化为了 $n-1$ 个数中选择若干个数，使得相邻两个数必须选一个，最小化选的数的和。

$f_{i,0/1}$ 为第 $i$ 个数选/不选的最小代价。

f_{i,0} = f_{i-1,1}= \min(f_{i-1,0} + \infty, f_{i-1,1} + 0)

f_{i,1} = \min(f_{i-1,0}, f_{i-1,1}) + w_i= \min(f_{i-1,0} + w_i, f_{i-1,1} + w_i)

写成矩阵乘法就是

\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 【模板】动态 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，已经不允许双 $\log$ 了。记：

\mathrm{Lsize}(u)=1+\sum \limits_{x\in \mathrm{LightSon}(u)} \mathrm{size}_x

此时，如果在每一条重链上以 $\mathrm{Lsize}$ 为权值，找到加权后的中点，左右递归建树维护信息，均摊复杂度是 $O(\log n)$ 的。（每条重链的根向着原树内的父亲建一条虚边）

#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 提高组] 保卫王国

模板是最大独立集，此题是最小覆盖集，并且要求 $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$ 。