【模板】动态dp

给定一棵n个点的树，点带点权。

有m次操作，每次操作给定x,y表示修改点x的权值为y。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

n,m<=1e5

参考题解：shadowice1984

n^2 DP简单又自然。

但是对于1e5次修改就不行了。

每一次修改会影响整个到根的链上的值。

采用树剖。

ldp[i][0/1]表示i选不选，对于所有的轻儿子dp值。

dp[i][0/1]表示i选不选，对于总共的所有儿子的dp值。

ldp[i][0]=∑max(ldp[lightson][1],ldp[lightson][0])

ldp[i][1]=∑ldp[lightson][0]

dp[i][0]=ldp[i][0]+max(dp[heavyson][1],dp[heavyson][0])

dp[i][1]=ldp[i][1]+dp[heavyson][0]

可以先把这个dp都求出来。

然后怎么维护？自然要用线段树维护dfs序。

采用矩阵。

a*b定义为：

c[i][j]=max(a[i][k]+b[k][j])

有结合律。

线段树维护区间矩阵乘积。（注意从右往左乘，自下而上）

只要在最前面乘上一个初始矩阵

第一行是0，第二行是-inf的矩阵。

就可以求出某个点的最终dp值了。

修改的时候，暴力修改这个点的ldp0，ldp1

但是还会影响这个fa[top[x]]的ldp0,ldp1

所以要求出dp[top[x]],dp[top[y]]为了避免常数过大，

用一个数组记录dp值，然后把前后两次最大值的差值来修改fa[top[x]]的ldp0,ldp1

然后跳一条链，到fa[top[x]]

这样单次修改log^2n

每次返回max(dp[1][0],dp[1][1])

普通线段树版：（3000ms）

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

#define mid ((l+r)>>1)

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=1e5+;

const int inf=0x3f3f3f3f;

int n,m;

struct node{

    int nxt,to;

}e[*N];

int hd[N],cnt;

void add(int x,int y){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    hd[x]=cnt;

}

struct tr{

    int a[][];

    void init(int x,int y){//x:ldp0 y:ldp1

        a[][]=x,a[][]=x;

        a[][]=y,a[][]=-inf;

    }

    void pre(){

        memset(a,-inf,sizeof a);

    }

    void st(){

        a[][]=,a[][]=-inf,a[][]=-inf,a[][]=;

    }

    tr operator *(const tr& b){

        tr c;c.pre();

        for(reg i=;i<=;++i){

            for(reg k=;k<=;++k){

                for(reg j=;j<=;++j){

                    c.a[i][j]=max(c.a[i][j],a[i][k]+b.a[k][j]);

                }

            }

        }return c;

    }

    void op(){

        cout<<left<<setw()<<a[][]<<" "<<left<<setw()<<a[][]<<endl;

        cout<<left<<setw()<<a[][]<<" "<<left<<setw()<<a[][]<<endl;

        cout<<endl;

    }

}s[N],t[*N],A;

int dfn[N],top[N],dfn2[N],fdfn[N],sz[N],dep[N],son[N];

int nd[N];//tot;//num of heavy chain

int fa[N];

int df;

int ldp[N][],dp[N][];

int w[N];

void dfs1(int x,int d){

    dep[x]=d;

    sz[x]=;

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa[x]) continue;

        fa[y]=x;

        dfs1(y,d+);

        if(sz[y]>sz[son[x]]){

            son[x]=y;

        }

    }

}

void dfs2(int x){

    dfn[x]=++df;fdfn[df]=x;

    if(!top[x]) {

        top[x]=x;nd[top[x]]=x;

    }

    if(son[x]) top[son[x]]=top[x],nd[top[x]]=son[x],dfs2(son[x]);

    dp[x][]=w[x];

    ldp[x][]=w[x];

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==son[x]||y==fa[x]) continue;

        dfs2(y);

        ldp[x][]+=max(dp[y][],dp[y][]);

        ldp[x][]+=dp[y][];

    }

    if(son[x]){

        dp[x][]=ldp[x][]+dp[son[x]][];

        dp[x][]=ldp[x][]+max(dp[son[x]][],dp[son[x]][]);

    }

    s[x].init(ldp[x][],ldp[x][]);

}

void pushup(int x){

    t[x]=t[x<<|]*t[x<<];

}

void build(int x,int l,int r){

    if(l==r){

        t[x]=s[fdfn[l]];return;

    }

    build(x<<,l,mid);build(x<<|,mid+,r);

    pushup(x);

}

tr query(int x,int l,int r,int L,int R){

    if(L<=l&&r<=R){

        return t[x];

    }

    tr ret;ret.st();

    if(mid<R) ret=ret*query(x<<|,mid+,r,L,R);

    if(L<=mid) ret=ret*query(x<<,l,mid,L,R);

    return ret;

}

void add(int x,int l,int r,int to,int p,int c){

    if(l==r){

        if(p) t[x].a[][]+=c;

        else t[x].a[][]+=c,t[x].a[][]+=c;

        return;

    }

    if(to<=mid) add(x<<,l,mid,to,p,c);

    else if(mid<to) add(x<<|,mid+,r,to,p,c);

    pushup(x);

}

int tmp[];

int to[];

int upda(int x,int y){

    tmp[]=tmp[]=;

    to[]=to[]=;

    tmp[]=y-w[x];

    w[x]=y;

    while(x){

        tr anc=A*query(,,n,dfn[top[x]],dfn[nd[top[x]]]);

        to[]=anc.a[][],to[]=anc.a[][];

        add(,,n,dfn[x],,tmp[]);

        add(,,n,dfn[x],,tmp[]);

        anc=A*query(,,n,dfn[top[x]],dfn[nd[top[x]]]);

        tmp[]=max(anc.a[][],anc.a[][])-max(to[],to[]);

        tmp[]=anc.a[][]-to[];

        x=fa[top[x]];

    }

    tr ans=A*query(,,n,dfn[top[]],dfn[nd[top[]]]);

    return max(ans.a[][],ans.a[][]);

}

int main(){

    scanf("%d%d",&n,&m);

    for(reg i=;i<=n;++i)rd(w[i]);

    int x,y;

    for(reg i=;i<=n-;++i){

        rd(x);rd(y);add(x,y);add(y,x);

    }

    dfs1(,);

    dfs2();

    build(,,n);

    A.a[][]=,A.a[][]=;

    A.a[][]=-inf,A.a[][]=-inf;

    while(m--){

        rd(x);rd(y);

        printf("%d\n",upda(x,y));

    }

    return ;

}

}

int main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/11/12 16:29:49

*/

zkw线段树版：（1500ms）

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

#define mid ((l+r)>>1)

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=1e5+;

const int inf=0x3f3f3f3f;

int n,m;

struct node{

    int nxt,to;

}e[*N];

int hd[N],cnt;

il void add(int x,int y){

    e[++cnt].nxt=hd[x];

    e[cnt].to=y;

    hd[x]=cnt;

}

struct tr{

    int a[][];

    void init(int x,int y){//x:ldp0 y:ldp1

        a[][]=x,a[][]=x;

        a[][]=y,a[][]=-inf;

    }

    void pre(){

        memset(a,-inf,sizeof a);

    }

    void st(){

        a[][]=,a[][]=-inf,a[][]=-inf,a[][]=;

    }

    tr operator *(const tr& b) const{

        tr c;c.pre();

        for(reg i=;i<=;++i){

            for(reg k=;k<=;++k){

                for(reg j=;j<=;++j){

                    c.a[i][j]=max(c.a[i][j],a[i][k]+b.a[k][j]);

                }

            }

        }return c;

    }

    void op(){

        cout<<left<<setw()<<a[][]<<" "<<left<<setw()<<a[][]<<endl;

        cout<<left<<setw()<<a[][]<<" "<<left<<setw()<<a[][]<<endl;

        cout<<endl;

    }

}s[N],t[*N],A;

int dfn[N],top[N],dfn2[N],fdfn[N],sz[N],dep[N],son[N];

int nd[N];//tot;//num of heavy chain

int fa[N];

int df;

int ldp[N][],dp[N][];

int w[N];

il void dfs1(int x,int d){

    dep[x]=d;

    sz[x]=;

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa[x]) continue;

        fa[y]=x;

        dfs1(y,d+);

        if(sz[y]>sz[son[x]]){

            son[x]=y;

        }

    }

}

il void dfs2(int x){

    dfn[x]=++df;fdfn[df]=x;

    if(!top[x]) {

        top[x]=x;nd[top[x]]=x;

    }

    if(son[x]) top[son[x]]=top[x],nd[top[x]]=son[x],dfs2(son[x]);

    dp[x][]=w[x];

    ldp[x][]=w[x];

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==son[x]||y==fa[x]) continue;

        dfs2(y);

        ldp[x][]+=max(dp[y][],dp[y][]);

        ldp[x][]+=dp[y][];

    }

    if(son[x]){

        dp[x][]=ldp[x][]+dp[son[x]][];

        dp[x][]=ldp[x][]+max(dp[son[x]][],dp[son[x]][]);

    }

    s[x].init(ldp[x][],ldp[x][]);

}

int up;

il void build(){

    up=;

    for(;up<=n+;up<<=);

    for(reg i=up;i<=up+up-;++i){

        if(i>=up+&&i<=up+n) t[i]=s[fdfn[i-up]];

        else t[i]=A;

    }

    for(reg i=up-;i;--i) t[i]=t[i<<|]*t[i<<];

}

il void chan(int to,int c0,int c1){

    reg i=up+to;

    t[i].a[][]+=c0;t[i].a[][]+=c0;

    t[i].a[][]+=c1;

    for(i>>=;i;i>>=){

        t[i]=t[i<<|]*t[i<<];

    }

//    cout<<" after chan "<<endl;

}

il tr query(int l,int r){

    tr le,ri;le.st();ri.st();

    for(reg s=up+l-,e=up+r+;s^e^;s>>=,e>>=){

//        cout<<s<<" "<<e<<endl;

        if(!(s&)) le=t[s^]*le;

        if(e&) ri=ri*t[e^];

    }

    return ri*le;

}

int tmp[];

int to[];

il int upda(int x,int y){

    tmp[]=tmp[]=;

    to[]=to[]=;

    tmp[]=y-w[x];

    w[x]=y;

    while(x){

        //tr anc=A*query(1,1,n,dfn[top[x]],dfn[nd[top[x]]]);

        to[]=dp[top[x]][],to[]=dp[top[x]][];

        chan(dfn[x],tmp[],tmp[]);

        tr anc=A*query(dfn[top[x]],dfn[nd[top[x]]]);

        tmp[]=max(anc.a[][],anc.a[][])-max(to[],to[]);

        tmp[]=anc.a[][]-to[];

        dp[top[x]][]=anc.a[][],dp[top[x]][]=anc.a[][];

        x=fa[top[x]];

    }

    return  max(dp[][],dp[][]);

}

int main(){

    scanf("%d%d",&n,&m);

    for(reg i=;i<=n;++i)rd(w[i]);

    int x,y;

    for(reg i=;i<=n-;++i){

        rd(x);rd(y);add(x,y);add(y,x);

    }

    dfs1(,);

    dfs2();

    A.a[][]=,A.a[][]=;

    A.a[][]=-inf,A.a[][]=-inf;

    build();

    while(m--){

        rd(x);rd(y);

        printf("%d\n",upda(x,y));

    }

    return ;

}

}

int main(){

//    freopen("data.in","r",stdin);

//    freopen("my.out","w",stdout);

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/11/12 16:29:49

*/

巴特西

[学习笔记]动态dp

【模板】动态dp

最新文章

热门文章