题解 P6021 【洪水】

· · 题解

题意

题目分析

显然是动态 DP。

据说这题珂以线段树二分但是我太蒻只会暴力 DDP

虽然题目中没有说明，但是这棵树以 1 号结点为根。

如果没有修改操作，这是一道简单的树形动规。

首先考虑没有修改操作的情况。

记 w_u 表示点 u 的权值， f_u 表示以 u 为根的子树的最小答案。
那么显然有

f_u = \min(w_u,\ \sum \limits _{v\in son_u} f_v)

方程的意义为：要么删去结点 u ，要么不删去结点 u ，在结点 u 的孩子中删去结点，两者取最小。

特殊的，对于叶结点，f_u = w_u 。

然后考虑修改点权的操作。

注意到每次修改点权只会对该结点到根的路径上的 f 值产生影响。
所以每次修改时暴力从该结点一直修改到 1 号结点。
最坏时间复杂度 \Theta (mn) ，稳稳地 TLE 。

接下来就需要请出主角：动态 DP 了。

动态 DP

动态 DP 用于解决一类被套上修改点权操作的基础 DP 题目。

其主要思想就是利用线段树维护每个结点的 DP 值。

但是由于大多数状态转移方程不满足结合律，所以无法直接使用线段树维护。

但是我们知道矩阵乘法运算是满足结合律的。

所以我们就需要把状态转移方程用矩阵乘法的形式表达出来。

模板题相信大家都过了。
不会动态 DP 的同学可以先去写一下这道模板题，里面的题解介绍的很详细。

构造矩阵

终于回到这题了。

让我们再来玩一玩刚才的状态转移方程。

f_u = \min(w_u,\ \sum \limits _{v\in son_u} f_v)

由于这是一棵树，所以先对它进行重链剖分，然后 按照套路 把轻儿子的答案的总和拎出来；也就是说，记 g_u 表示以 u 为根的子树中轻儿子的答案总和，则可以将原方程转化为：

f_u = \text{min}(w_u,\ f_{son_u}+g_u)

然后考虑把这个方程转化为矩阵乘法的形式。

在这里，我们需要重新定义一下矩阵乘法：对于矩阵 A ，B ，若矩阵 C 满足 C=A*B ，则有：

C_{i,j}=\min \limits _k (A_{i,k}+B_{k,j})

至于这个运算为什么满足结合律，请读者自行验证。

那么我们相当于要找到一个转移矩阵 U ，使得 ：

\begin{pmatrix} f_{son_u} \\ 0 \end{pmatrix} * U = \begin{pmatrix} f_{u} \\ 0 \end{pmatrix}

注意新定义的矩阵乘法不满足交换律。说的好像原来的矩阵乘法满足交换律一样。

首先 U 是一个 2 \times2 的矩阵。
根据新定义的矩阵乘法，可以得出：

  1. f_u=\min(f_{son_u}+U_{1,1}, 0+U_{1,2})
  2. 0 = \min(f_{son_u}+U_{2,1}, 0+U_{2,2})

再结合原方程，即可得出

* \begin{pmatrix} g_u & w_u \\ \infty & 0 \end{pmatrix} = \begin{pmatrix} f_{u} \\ 0 \end{pmatrix}

然后用线段树维护转移矩阵就可以了。

在实现时我使用了一个矩阵数组来记录转移矩阵，听说这样可以减常数。

另外由于我太蒻了，写的树剖常数大，所以这份代码需要吸氧才能通过。

Code

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;
const int MAXN = 200010;
const ll INF = 1e17+1;

int n, m;;

struct edge{
    int ne, to;
}e[MAXN<<1];
int fir[MAXN], num = 0;
inline void join(int a, int b)
{
    e[++num].ne = fir[a];
    fir[a] = num;
    e[num].to = b;
}

struct mat{
    ll ele[2][2];
    mat(int type = 0)
    {
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                ele[i][j] = INF;
        if(type == 1) {
            for(int i=0;i<2;i++)
                ele[i][i] = 0;
        }
    }
    ll& operator()(const int ix, const int iy){return ele[ix][iy];}
    // 重定义的矩阵乘法
    inline friend mat operator*(mat mx, mat my)
    {
        mat res(0);
        for(int i=0;i<2;i++)
            for(int k=0;k<2;k++)
                for(int j=0;j<2;j++)
                    res(i,j)=min(res(i,j), mx(i,k)+my(k,j));
        return res;
    }
};

ll val[MAXN], f[MAXN];
mat g[MAXN];

int dep[MAXN], pa[MAXN], siz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rev[MAXN], end[MAXN], cnt = 0;

void dfs1(int u, int fa)
{
    siz[u] = 1; dep[u] = dep[fa] + 1; pa[u] = fa;
    for(int i=fir[u];i;i=e[i].ne)
    {
        int v = e[i].to;
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
}
void dfs2(int u, int t)
{
    dfn[u] = ++cnt; rev[cnt] = u; top[u] = t; end[t] = max(end[t], cnt);
    g[u](0, 0) = 0;   g[u](0, 1) = val[u];
    g[u](1, 0) = INF; g[u](1, 1) = 0;
    f[u] = 0;
    if(son[u]) {

        dfs2(son[u], t);
        f[u] += f[son[u]];
    }
    else g[u](0, 0) = INF; //为了保证叶结点转移的合法
    for(int i=fir[u];i;i=e[i].ne)
    {
        int v = e[i].to;
        if(v == pa[u] || v == son[u]) continue;
        dfs2(v, v);
        g[u](0, 0) += f[v]; //g 数组的转移不包括重儿子
        f[u] += f[v];
    }
    if(!son[u]) f[u] = val[u]; // 特判叶结点
    else f[u] = min(f[u], val[u]); // 记得两者取最小
}
struct {
    int l, r;
    mat val;
}t[MAXN<<2];
inline void pushUp(int k)
{
    t[k].val = t[k<<1].val*t[k<<1|1].val;
}
void build(int l, int r, int k)
{
    t[k].l = l; t[k].r = r;
    if(l == r) {
        t[k].val = g[rev[l]];
        return ;
    }
    int mid = t[k].l+t[k].r>>1;
    build(l, mid, k<<1);
    build(mid+1, r, k<<1|1);
    pushUp(k);
}
void update(int x, int k)
{
    if(t[k].l == t[k].r) {
        t[k].val = g[rev[x]]; //由于有在树外记录转移矩阵，直接赋值即可
        return ;
    }
    int mid = t[k].l+t[k].r>>1;
    if(x <= mid) update(x, k<<1);
    else update(x, k<<1|1);
    pushUp(k);
}
mat query(int x, int y, int k)
{
    if(t[k].l == x && t[k].r == y) return t[k].val;
    int mid = t[k].l+t[k].r>>1;
    if(y <= mid) return query(x, y, k<<1);
    else if(x >= mid+1) return query(x, y, k<<1|1);
    else return query(x, mid, k<<1)*query(mid+1, y, k<<1|1);
}
inline void updatePath(int x, ll z)
{
    val[x] += z;
    g[x](0, 1) = val[x];
    mat bef, aft;
    while(x)
    {
        bef = query(dfn[top[x]], end[top[x]], 1);
        // 记录更新之前的矩阵
        update(dfn[x], 1);
        aft = query(dfn[top[x]], end[top[x]], 1);
        x = pa[top[x]];
        g[x](0, 0) += min(aft(0, 0), aft(0, 1)) - min(bef(0, 0), bef(0, 1)); 
        // 更新转移矩阵，为下一条链的修改做准备，注意这里需要先减去原先的值
    }
}
inline ll querySubtree(int x)
{
    mat res = query(dfn[x], end[x], 1); // 查询时只需要从当前点到链尾即可
    return min(res(0, 0), res(0, 1));
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%lld",&val[i]);
    for(int i=1;i<n;i++)
    {
        int a, b;
        scanf("%d%d",&a,&b);
        join(a, b);
        join(b, a);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    for(int i=1;i<=n;i++)
        end[i] = end[top[i]];
    build(1, n, 1);
    scanf("%d",&m);
    while(m--)
    {
        char opt; int x; ll z;
        cin>>opt;
        if(opt == 'C') {
            scanf("%d%lld",&x,&z);
            updatePath(x, z);
        }
        else {
            scanf("%d",&x);
            printf("%lld\n",querySubtree(x));
        }
    }
    return 0;
}