动态dp 板子

动态dp

瞎扯两句吧

先从序列上理解，维护链的最大独立集。

考虑是从左边转移的，那么矩阵的转移唯一，直接放在线段树上就可以了。

放在树上的话，儿子都可以转移，把轻儿子的转移放在子链链头更新，然后每条链都处理成序列就行了。

注意一点，因为维护的是序列，所以单点存放的矩阵是只含轻儿子和自己的贡献，相当于把轻儿子的子树缩给了自己，而重儿子维护的东西是通过线段树上维护的区间贡献过来的。

咕咕模板，最大全独立集

Code:

#include <cstdio>

#include <algorithm>

#include <cctype>

using std::max;

const int N=1e5+10;

const int inf=0x3f3f3f3f;

int n,m,v[N];

int read()

{

    int x=0,f=1;char c=getchar();

    while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

    while(isdigit(c)) {x=x*10+c-'0';c=getchar();}

    return x*f;

}

int head[N],to[N<<1],Next[N<<1],cnt;

void add(int u,int v)

{

    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

int dfn[N],top[N],bot[N],siz[N],ha[N],f[N],ws[N],dfsclock,dp[N][2],len;

void dfs1(int now)

{

    ++siz[now],dp[now][1]=v[now];

    for(int v,i=head[now];i;i=Next[i])

        if((v=to[i])!=f[now])

        {

            f[v]=now,dfs1(v),siz[now]+=siz[v];

            dp[now][1]+=dp[v][0];

            dp[now][0]+=max(dp[v][0],dp[v][1]);

            if(siz[v]>siz[ws[now]]) ws[now]=v;

        }

}

void dfs2(int now,int anc)

{

    ha[dfn[now]=++dfsclock]=now;

    bot[top[now]=anc]=now;

    if(ws[now]) dfs2(ws[now],anc);

    for(int v,i=head[now];i;i=Next[i])

        if(!dfn[v=to[i]])

            dfs2(v,v);

    bot[now]=bot[anc];

}

struct matrix{int dx[2][2];}mx[N<<2],upt[N];

matrix operator *(matrix a,matrix b)

{

    matrix ret;

    ret.dx[0][0]=max(a.dx[0][0]+b.dx[0][0],a.dx[0][1]+b.dx[1][0]);

    ret.dx[0][1]=max(a.dx[0][0]+b.dx[0][1],a.dx[0][1]+b.dx[1][1]);

    ret.dx[1][0]=max(a.dx[1][0]+b.dx[0][0],a.dx[1][1]+b.dx[1][0]);

    ret.dx[1][1]=max(a.dx[1][0]+b.dx[0][1],a.dx[1][1]+b.dx[1][1]);

    return ret;

}

#define ls id<<1

#define rs id<<1|1

void build(int id,int l,int r)

{

    if(l==r)

    {

        int now=ha[l],g0=0,g1=v[now];

        for(int v,i=head[now];i;i=Next[i])

            if((v=to[i])!=ws[now]&&v!=f[now])

                g0+=max(dp[v][0],dp[v][1]),g1+=dp[v][0];

        upt[l]=mx[id]=(matrix){g0,g0,g1,-inf};

        return;

    }

    int mid=l+r>>1;

    build(ls,l,mid),build(rs,mid+1,r);

    mx[id]=mx[ls]*mx[rs];

}

matrix query(int id,int L,int R,int l,int r)

{

    if(l==L&&r==R) return mx[id];

    int Mid=L+R>>1;

    if(r<=Mid) return query(ls,L,Mid,l,r);

    else if(l>Mid) return query(rs,Mid+1,R,l,r);

    else return query(ls,L,Mid,l,Mid)*query(rs,Mid+1,R,Mid+1,r);

}

void change(int id,int l,int r,int p)

{

    if(l==r) {mx[id]=upt[l];return;}

    int mid=l+r>>1;

    if(p<=mid) change(ls,l,mid,p);

    else change(rs,mid+1,r,p);

    mx[id]=mx[ls]*mx[rs];

}

void modify(int now,int w)

{

    upt[dfn[now]].dx[1][0]+=w-v[now],v[now]=w;

    while(233)

    {

        matrix a=query(1,1,n,dfn[top[now]],dfn[bot[now]]);

        change(1,1,n,dfn[now]);

        matrix b=query(1,1,n,dfn[top[now]],dfn[bot[now]]);

        now=f[top[now]];

        if(!now) break;

        upt[dfn[now]].dx[0][0]+=max(b.dx[0][0],b.dx[1][0])-max(a.dx[0][0],a.dx[1][0]);

        upt[dfn[now]].dx[0][1]=upt[dfn[now]].dx[0][0];

        upt[dfn[now]].dx[1][0]+=b.dx[0][0]-a.dx[0][0];

    }

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=n;i++) v[i]=read();

    for(int u,v,i=1;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);

    dfs1(1),dfs2(1,1),build(1,1,n);

    for(int u,w,i=1;i<=m;i++)

    {

        u=read(),w=read();

        modify(u,w);

        matrix ans=query(1,1,n,1,dfn[bot[1]]);

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

    }

    return 0;

}

2019.1.2

巴特西

动态dp 板子

动态dp

最新文章

热门文章