洛谷P4719 【模板】"动态 DP"&动态树分治

时间：2023-12-31 15:26:20

【模板】"动态 DP"&动态树分治

第一道动态\(DP\)的题，只会用树剖来做，全局平衡二叉树什么的就以后再学吧

所谓动态\(DP\)，就是在原本的\(DP\)求解的问题上加上修改操作，从而使得问题变成动态的问题

这道题的问题就是普通的树形\(DP\)上加上了修改点权的操作

题意：

给定一棵 \(n\) 个点的树。\(i\) 号点的点权为 \(a_i\)。有 \(m\) 次操作，每次操作给定 \(u\),\(w\)，表示修改点 \(u\) 的权值为 \(w\)。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

考虑最暴力的做法，每次修改点权之后暴力求解，复杂度\(O(nm)\)

稍微做一点优化，可以发现每次修改值之后，只有修改的点到根的路径上的点的\(dp\)值会发生改变，所以只更新路径上的点的\(dp\)值就好了，但是如果树退化成链的话，复杂度还是\(O(nm)\)的

令\(f[u][0]\)为不选择\(u\)点的情况下以\(u\)为根的子树的独立集的最大值，\(f[u][1]\)为选择\(u\)点的情况下以\(u\)为根的子树的独立集的最大值

先把转移方程列出来：

\[\begin{cases}f[u][0] = \sum_{v\in son_u}\max(f[v][0],f[v][1]) \\ f[u][1] = A[u] + \sum_{v\in son_u} f[v][0] \end{cases}
\]

如果对原树进行轻重链剖分，对于每个点只存在一个重儿子

那么我们令\(\begin{cases} g[u][0]=\sum_{v\in lson_u}\max(f[v][0],f[v][1])\\ g[u][1] = A[u] + \sum_{v\in lson_u} f[v][0]\end{cases}\)

其中\(v\in lson_u\)表示\(v\)是\(u\)的轻儿子

然后我们单独考虑重儿子\(hv\)，可以得到\(\begin{cases}f[u][0] = g[u][0] + max(f[hv][0],f[hv][1]) \\ f[u][1] = g[u][1] + f[hv][0]\end{cases}\)

这样的\(dp\)转移一般可以用矩阵来表示，然后用矩阵连乘来把转移矩阵乘起来快速得到答案，但是这里的转移和一般的转移不同，我们考虑一个新的矩阵运算：

\[\left[
\begin{array}{c}
a_{11}& a_{12}\\
\end{array}
\right ]

\cdot

\left[
\begin{array}{cc}
b_{11}& b_{12}\\
b_{21}& b_{22}\\
\end{array}
\right ]

=

\left[

\begin{array}{c}
\max(a_{11} + b_{11},a_{12} + b_{21}) &
\max(a_{11} + b_{12},a_{12} + b_{22})
\end{array}

\right]
\]

那么我们就可以用矩阵的形式来表示转移了：

\[\left[

\begin{array}{c}
f[i][0] & f[i][1]
\end{array}

\right]
=

\left[
\begin{array}{c}
f[hv][0]& f[hv][1]\\
\end{array}
\right]

\cdot

\left[
\begin{array}{cc}
g[i][0]& g[i][1]\\
g[i][0]& -\infty\\
\end{array}
\right]

\]

由于重儿子不计算在这个转移矩阵内，所以每次修改的时候我们从下往上，每次到重链顶部的时候，跳一下轻链，只要修改这个点的转移矩阵就好了，链数不会超过\(\log n\)，而这个转移矩阵的区间乘积可以用线段树来维护，所以总复杂度是\(O(n\log^2 n)\)

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 1e5+7;

struct Matrix{

    int mat[2][2];

    Matrix(){ memset(mat,-0x3f,sizeof(mat)); }

    Matrix operator * (const Matrix &rhs) const{

        Matrix ret;

        for(int i = 0; i < 2; i++)

            for(int j = 0; j < 2; j++)

                for(int k = 0; k < 2; k++)

                    ret.mat[i][j] = max(ret.mat[i][j],mat[i][k] + rhs.mat[k][j]);

        return ret;

    }

};

int n, m, par[MAXN], A[MAXN];

int top[MAXN], dep[MAXN], sz[MAXN], dfn[MAXN], rdfn[MAXN], son[MAXN], tail[MAXN], idx;

vector<int> G[MAXN];

Matrix w[MAXN];

struct SegmentTree{

    Matrix M[MAXN<<2];

    int l[MAXN<<2], r[MAXN<<2];

    #define ls(rt) rt << 1

    #define rs(rt) rt << 1 | 1

    void pushup(int rt){ M[rt] = M[rs(rt)] * M[ls(rt)]; }

    void build(int L, int R, int rt = 1){

        l[rt] = L; r[rt] = R;

        if(L+1==R){

            M[rt] = w[rdfn[L]];

            return;

        }

        int mid = (L + R) >> 1;

        build(L,mid,ls(rt)); build(mid,R,rs(rt));

        pushup(rt);

    }

    void update(int pos, Matrix &MT, int rt = 1){

        if(l[rt] + 1 == r[rt]){

            M[rt] = MT;

            return;

        }

        int mid = (l[rt] + r[rt]) >> 1;

        if(pos<mid) update(pos,MT,ls(rt));

        else update(pos,MT,rs(rt));

        pushup(rt);

    }

    Matrix query(int L, int R, int rt = 1){

        if(L<=l[rt] and r[rt]<=R) return M[rt];

        int mid = (l[rt] + r[rt]) >> 1;

        if(mid <= L) return query(L,R,rs(rt));

        else if(R <= mid) return query(L,R,ls(rt));

        else return query(L,R,rs(rt)) * query(L,R,ls(rt));

    }

}ST;

void dfs1(int u, int fa){

    dep[u] = dep[par[u] = fa] + 1;

    sz[u] = 1; son[u] = 0;

    for(int v : G[u]){

        if(v==fa) continue;

        dfs1(v,u);

        sz[u] += sz[v];

        if(sz[v] > sz[son[u]]) son[u] = v;

    }

}

int f[MAXN][2];

void dfs2(int u, int tp){

    dfn[u] = ++idx;

    rdfn[idx] = u;

    top[u] = tp;

    tail[tp] = u;

    w[u].mat[0][0] = w[u].mat[1][0] = 0;

    w[u].mat[0][1] = A[u];

    f[u][0] = 0;

    f[u][1] = A[u];

    if(son[u]){

        dfs2(son[u],tp);

        f[u][0] += max(f[son[u]][0],f[son[u]][1]);

        f[u][1] += f[son[u]][0];

    }

    for(int v : G[u]){

        if(v==par[u] or v==son[u]) continue;

        dfs2(v,v);

        f[u][0] += max(f[v][0],f[v][1]);

        f[u][1] += f[v][0];

        w[u].mat[0][0] += max(f[v][0],f[v][1]);

        w[u].mat[1][0] += max(f[v][0],f[v][1]);

        w[u].mat[0][1] += f[v][0];

    }

}

void update(int u, int x){

    w[u].mat[0][1] += x - A[u];

    A[u] = x;

    while(u){

        Matrix bef = ST.query(dfn[top[u]],dfn[tail[top[u]]]+1);

        ST.update(dfn[u],w[u]);

        Matrix aft = ST.query(dfn[top[u]],dfn[tail[top[u]]]+1);

        u = par[top[u]];

        w[u].mat[0][0] -= max(bef.mat[0][0],bef.mat[0][1]) - max(aft.mat[0][0],aft.mat[0][1]);

        w[u].mat[1][0] = w[u].mat[0][0];

        w[u].mat[0][1] -= bef.mat[0][0] - aft.mat[0][0];

    }

}

void solve(){

    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);

    }

    dfs1(1,0); dfs2(1,1);

    ST.build(1,n+1);

    while(m--){

        int u, x;

        cin >> u >> x;

        update(u,x);

        Matrix ret = ST.query(dfn[1],dfn[tail[1]]+1);

        printf("%d\n",max(ret.mat[0][0],ret.mat[0][1]));

    }

}

int main(){

    #ifndef ONLINE_JUDGE

    freopen("Local.in","r",stdin);

    freopen("ans.out","w",stdout);

    #endif

    ____();

    solve();

    return 0;

}

相关文章