bzoj 4712 洪水

题意

显然有这个DP：
设\(f_x\)表示封住\(x\)的子树的最小代价。
显然有：
\(f_x=\min(\sum\limits_{y\in son_x}f_y,a_x)\)

现在考虑用动态DP：
设\(g_x\)表示\(x\)除去的重儿子的\(f_x\)。
有：
\(f_x=\min(g_x+f_{heavyson_x},a_x)\)
写成矩阵的形式就是：
\(\begin{bmatrix}f_{heavyson_x},0\end{bmatrix}\begin{bmatrix}g_x,inf\\ a_x,0\end{bmatrix}=\begin{bmatrix}f_x,0\end{bmatrix}\)
于是可以树剖了，注意先乘右儿子再乘左儿子，因为初始值在叶子，也就是链尾。
code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
const int maxn=200010;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,cnt,tim;
int head[maxn],a[maxn],dfn[maxn],pos[maxn],pre[maxn],son[maxn],dep[maxn],size[maxn],top[maxn],ed[maxn],f[maxn],g[maxn];
struct edge{int to,nxt;}e[maxn<<1];
struct Mat
{
    int a[5][5];
    Mat(){memset(a,0x3f,sizeof(a));}
    int* operator[](const int i){return a[i];}
}seg[maxn<<2],val[maxn];
Mat operator*(Mat a,Mat b)
{
    Mat res;
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++)
                res[i][j]=min(res[i][j],a[i][k]+b[k][j]);
    return res;
}
inline void add(int u,int v)
{
    e[++cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
}
void dfs1(int x,int fa)
{
    dep[x]=dep[fa]+1;size[x]=1;pre[x]=fa;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==fa)continue;
        dfs1(y,x);size[x]+=size[y];
        if(size[y]>size[son[x]])son[x]=y;
    }
}
void dfs2(int x,int tp)
{
    dfn[x]=++tim;pos[tim]=x;top[x]=tp;ed[tp]=x;
    if(son[x])dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==pre[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
void dp(int x,int fa)
{
    f[x]=a[x];
    if(son[x])dp(son[x],x),f[x]=min(f[x],f[son[x]]);
    else g[x]=inf;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int y=e[i].to;
        if(y==pre[x]||y==son[x])continue;
        dp(y,x);g[x]+=f[y];
    }
    f[x]=min(f[x]+g[x],a[x]);
    val[x][1][1]=g[x],val[x][1][2]=inf,val[x][2][1]=a[x],val[x][2][2]=0;
}
inline void up(int p){seg[p]=seg[rs(p)]*seg[ls(p)];}
void build(int p,int l,int r)
{
    if(l==r){seg[p]=val[pos[l]];return;}
    int mid=(l+r)>>1;
    build(ls(p),l,mid);build(rs(p),mid+1,r);
    up(p);
}
void change(int p,int l,int r,int k)
{
    if(l==r){seg[p]=val[pos[l]];return;}
    int mid=(l+r)>>1;
    if(k<=mid)change(ls(p),l,mid,k);
    else change(rs(p),mid+1,r,k);
    up(p);
}
Mat query(int p,int l,int r,int ql,int qr)
{
    if(l>=ql&&r<=qr)return seg[p];
    int mid=(l+r)>>1;
    if(qr<=mid)return query(ls(p),l,mid,ql,qr);
    else if(ql>mid)return query(rs(p),mid+1,r,ql,qr);
    else return query(rs(p),mid+1,r,ql,qr)*query(ls(p),l,mid,ql,qr);
}
inline int query(int x)
{   
    Mat res=query(1,1,n,dfn[x],dfn[ed[top[x]]]);
    return min(res[1][1],res[2][1]);
}
inline void change(int x,int k)
{
    a[x]+=k;
    while(x)
    {
        val[x][1][1]=g[x],val[x][1][2]=inf,val[x][2][1]=a[x],val[x][2][2]=0;
        change(1,1,n,dfn[x]);
        x=top[x];
        if(x==1)break;
        g[pre[x]]-=f[x];f[x]=query(x);g[pre[x]]+=f[x];
        x=pre[x];
    }
}
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%lld%lld",&u,&v);
        add(u,v),add(v,u);              
    }
    dfs1(1,0);dfs2(1,1);dp(1,0);
    build(1,1,n);
    scanf("%lld",&m);
    for(int i=1;i<=m;i++)
    {
        char op[5];scanf("%s",op);
        int x,k;
        if(op[0]=='Q')scanf("%lld",&x),printf("%lld\n",query(x));
        else scanf("%lld%lld",&x,&k),change(x,k);
    }
    return 0;
}

bzoj 4712 洪水

原文：https://www.cnblogs.com/nofind/p/12013503.html