树形DP

Author Avatar
Axell 2月 06, 2019
  • 在其它设备中阅读本文章

树形DP

需要进行树形的DP算法，通常是由于状态存在顺序，循环无法进行，这种情况下，可以用递归的形式，把状态看成一张图，按照拓扑序进行DP

代码实现

通常分为以下几步

  1. 构建一颗树
  2. 从树根开始进行深搜，先递归搜索完一个点的所有子节点后，得到这个点的最优答案，最终得到根节点的最优解

例题

没有上司的舞会P287
用F[x][0]表示x节点不参与的最大答案，F[x][1]表示参与的最大答案，则可以很容易推出状态转移方程

#include <bits/stdc++.h>
using namespace std;

int n,Next[6005],head[6005],en[6005],f[6005][2],cnt;
struct node{
    int v,fa;
}a[6005];

void add(int x,int y){
    cnt++;
    Next[cnt]=head[x];
    head[x]=cnt;
    en[cnt]=y;
}

int dfs(int x,bool in){
    if (f[x][in]>=-1e7) return f[x][in];
    int ans=0;
    if (in){
        for (int i=head[x];i!=0;i=Next[i]){
            ans+=dfs(en[i],0);
        }
        ans+=a[x].v;
    }else{
        for (int i=head[x];i!=0;i=Next[i]){
            ans+=max(dfs(en[i],0),dfs(en[i],1));
        }
    }
    f[x][in]=ans;
    return ans;
}

int main(){
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d",&a[i].v);
    for (int i=1;i<=n-1;++i){
        int x,y;
        scanf("%d %d",&x,&y);
        a[x].fa=y;
        add(y,x);
    }
    int rt=0;
    for (int i=1;i<=n;++i) if (a[i].fa==0) rt=i;
    memset(f,0x80,sizeof f);
    printf("%d\n",max(dfs(rt,0),dfs(rt,1)));
    return 0;
}

稀有矿井
状压+树形DP
F[i][j]表示以i为根的子树中，获得j状态的金属的最小花费
动规方程如下：
$$F_{x,j|k}=min(F_{y,k}+F_{y,j}+E_{x,y})$$
注意，这题不需要用到换根法，因为这题的要求是选出树中的一部分，而不在乎谁是根，因此最优解一定可以在某个点以下的子树中被找到

#include <bits/stdc++.h>
using namespace std;

int f[1001][32],a[1001],n,Next[2001],head[2001],en[2001],V[2001],cnt;

void add(int x,int y,int v){
    cnt++;
    Next[cnt]=head[x];
    head[x]=cnt;
    en[cnt]=y;
    V[cnt]=v;
}

void dfs(int rt,int fa){
    for (int i=head[rt];i;i=Next[i]){
        int y=en[i];
        if (y==fa) continue;
        dfs(y,rt);
        for (int j=0;j<=31;++j){
            for (int k=0;k<=31;++k){
                f[rt][j|k]=min(f[rt][j|k],f[rt][j]+f[y][k]+V[i]);
            }
        }
        f[rt][31]=min(f[rt][31],f[y][31]);
    }
}

void solve(){
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    memset(f,0x3f,sizeof f);
    memset(head,0,sizeof head);
    cnt=0;
    for (int i=1;i<n;++i){
        int x,y,v;
        scanf("%d %d %d",&x,&y,&v);
        add(x,y,v);
        add(y,x,v);
    }
    for (int i=1;i<=n;++i){
        if (a[i]){
            f[i][1<<(a[i]-1)]=0;
        }
        f[i][0]=0;
    }
    dfs(1,0);
    printf("%d\n",f[1][31]);
}

int main(){
    int t;
    cin>>t;
    while (t--) solve();
    return 0;
}

树形背包问题

只是把状态转移方程转移到树上，F[i][j]可以由F[x][]推得，其中x是i的儿子，除了节点编号这一状态，通常还有当前背包的体积最为第二维状态

例题

选课P289
直接在原始的多叉树上执行分组背包的模型，添加一个虚拟节点0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,m,Next[305],head[305],en[305],f[305][305],cnt;

void add(int x,int y){
    cnt++;
    Next[cnt]=head[x];
    head[x]=cnt;
    en[cnt]=y;
}

struct node{
    int f,v;
}a[305];

void dfs(int x){
    f[x][0]=0;
    for (int i=head[x];i!=0;i=Next[i]){
        int y=en[i];
        dfs(y);
        for (int j=m;j>=0;--j){  //枚举算上x选了几个点
            for (int k=j;k>=0;--k){
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);  //枚举子节点选了几个
            }
        }
    }
    if (x){
        for (int i=m;i>=1;--i) f[x][i]=f[x][i-1]+a[x].v;
    } // 因为x必须选择，否则子节点选不了
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i) scanf("%d %d",&a[i].f,&a[i].v),add(a[i].f,i);
    memset(f,0xcf,sizeof f);
    dfs(0);
    cout<<f[0][m]<<endl;
    return 0;
}

二次扫描和换根法

对于不定根的树形DP问题，普通做法是枚举每一个节点作为根节点，复杂度过高
可以先定一个点为根节点，进行一次DP，再用一次DFS，求出当其它点作为根节点时的答案，详见P290

例题

水系流量

#include <bits/stdc++.h>
using namespace std;

int cnt,n,Next[400005],head[200005],en[400005],V[400005],f[200005],g[200005],d[200005],ans;

void add(int x,int y,int v){
    cnt++;
    Next[cnt]=head[x];
    head[x]=cnt;
    en[cnt]=y;
    V[cnt]=v;
}

void dp(int rt,int fa){
    for (int i=head[rt];i;i=Next[i]){
        int y=en[i];
        if (y==fa) continue;
        dp(y,rt);
        if (d[y]==1) f[rt]+=V[i];
        else f[rt]+=min(f[y],V[i]);
    }
}

void dfs(int rt,int fa){
    for (int i=head[rt];i;i=Next[i]){
        int y=en[i];
        if (y==fa) continue;
        if (d[rt]==1) g[y]=f[y]+V[i];
        else g[y]=f[y]+min(V[i],g[rt]-min(V[i],f[y]));
        dfs(y,rt);
    }
}

void solve(){
    cin>>n;
    memset(head,0,sizeof head);
    memset(d,0,sizeof d);
    memset(g,0,sizeof g);
    memset(f,0,sizeof f);
    cnt=0;
    int x,y,v;
    for (int i=1;i<=n-1;++i){
        scanf("%d %d %d",&x,&y,&v);
        add(x,y,v);
        add(y,x,v);
        d[x]++,d[y]++;
    }
    dp(1,0);
    g[1]=f[1];
    dfs(1,0);
    ans=0;
    for (int i=1;i<=n;++i) ans=max(ans,g[i]);
    printf("%d\n",ans);
}

int main(){
    int t;
    cin>>t;
    while (t--) solve();
}

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/93/