今天学习了树形\(dp\)，一开始浏览各大\(blog\)，发现都\(TM\)是题，连个入门的\(blog\)都没有，体验极差。所以我立志要写一篇可以让初学树形\(dp\)的童鞋快速入门。

树形\(dp\)

概念类

树形\(dp\)是一种很优美的动态规划，真的很优美真的，前提是在你学会它之后。

实现形式

树形\(dp\)的主要实现形式是\(dfs\)，在\(dfs\)中\(dp\)，主要的实现形式是\(dp[i][j][0/1]\)，\(i\)是以\(i\)为根的子树，\(j\)是表示在以\(i\)为根的子树中选择\(j\)个子节点，\(0\)表示这个节点不选，\(1\)表示选择这个节点。有的时候\(j\)或\(0/1\)这一维可以压掉

基本的\(dp\)方程

选择节点类

\[\begin{cases}
dp[i][0]=dp[j][1]
\\
dp[i][1]=\max/\min(dp[j][0],dp[j][1])\\
\end{cases}
\]

树形背包类

\[\begin{cases}
dp[v][k]=dp[u][k]+val\\
dp[u][k]=max(dp[u][k],dp[v][k-1])\\
\end{cases}
\]

例题类

以上就是对树形\(dp\)的基本介绍，因为树形\(dp\)没有基本的形式，然后其也没有固定的做法，一般一种题目有一种做法。

没有上司的舞会

这道题是一树形\(dp\)入门级别的题目，具体方程就用到了上述的选择方程。

#include<cmath>

#include<cstdio>

#include<iostream>

#include<algorithm>

#define N 6001

using namespace std;

int ind[N],n,hap[N],dp[N][2],fa[N],root,vis[N],ne[N],po[N];

void work(int x)

{

    for(int i = po[x]; i; i = ne[i])

    {

        work(i);

        dp[x][1]=max(max(dp[x][1],dp[x][1]+dp[i][0]),dp[i][0]);

        dp[x][0]=max(max(dp[x][0],dp[i][1]+dp[x][0]),max(dp[i][1],dp [i][0]));

    }

}

int main()

{

    cin >> n;

    for(int i=1; i<=n; i++)

        cin >> dp[i][1];

    for(int i=1; i<=n; i++)

    {

        int a,b;

        cin >> b >> a;

        ind[b]++;

        ne[b] = po[a];

        po[a] = b;

    }

    for(int i=1; i<=n; i++)

        if(!ind[i])

        {

            root=i;

            break;

        }

    work(root);

    cout << max(dp[root][0],dp[root][1]);

}

最大子树和

这道题的\(dp\)方程有变，因为你的操作是切掉这个点，所以你的子树要么加上价值，要么价值为\(0\)，所以\(dp\)方程是

\[dp[u]+=max(dp[v],0)
\]

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

struct edge

{

    int next,to;

} e[40000];

int head[40000],tot,rt,maxn;

void add(int x,int y)

{

    e[++tot].next=head[x];

    head[x]=tot;

    e[tot].to=y;

}

int n,dp[20000],ind[20000];

int val[20000],f[20000];

void dfs_f__k(int x,int fa)

{

    f[x]=fa;

    for(int i=head[x]; i; i=e[i].next)

    {

        int v=e[i].to;

        if(v!=fa)

            dfs_f__k(v,x);

    }

}

void dfs(int x)

{

    dp[x]=val[x];

    for(int i=head[x]; i; i=e[i].next)

    {

        int v=e[i].to;

        if(v!=f[x])

        {

            dfs(v);

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

        }

    }

    maxn=max(maxn,dp[x]);

}

int main()

{

    scanf("%d",&n);

    for(int i=1; i<=n; i++)scanf("%d",&val[i]);

    for(int i=1; i<=n-1; i++)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        add(a,b);

        add(b,a);

    }

    rt=1;

    dfs_f__k(rt,0);

    dfs(rt);

    printf("%d",maxn);

}

选课

这道题的意思是每本书要想选择一门课，必须要先学会它的必修课，所以这就形成了一种依赖行为，即选择一门课必须要选择必修课。那么他又说要选择的价值最大，这就要用到树形背包的知识了。

树形背包的基本代码形式（即上面的树形背包类）

/*

设dp[i][j]表示选择以i为根的子树中j个节点。

u代表当前根节点，tot代表其选择的节点的总额。

*/

void dfs(int u,int tot)

{

	for(int i=head[x];i;i=e[i].next)

	{

		int v=e[i].to;

		for(int k=0;k<tot;k++)//这里k从o开始到tot-1，因为v的子树可以选择的节点是u的子树的节点数减一

			dp[v][k]=dp[u][k]+val[u];

		dfs(v,tot-1)

		for(int k=1;k<=tot;k++)

			dp[u][k]=max(dp[u][k],dp[v][k-1]);//这里是把子树的值赋给了根节点，因为u选择k个点v只能选择k-1个点。

	}

}

然后这就是树形背包的基本形式，基本就是这样做

代码

#include<iostream>

#include<algorithm>

#include<queue>

#include<cstdio>

#include<cstring>

using namespace std;

int n,m;

struct edge

{

    int next,to;

}e[1000];

int rt,head[1000],tot,val[1000],dp[1000][1000];

void add(int x,int y)

{

    e[++tot].next=head[x];

    head[x]=tot;

    e[tot].to=y;

}

void dfs(int u,int t)

{

    if (t<=0) return ;

    for (int i=head[u]; i; i=e[i].next)

    {

        int v = e[i].to;

        for (int k=0; k<t; ++k)

            dp[v][k] = dp[u][k]+val[v];

        dfs(v,t-1);

        for (int k=1; k<=t; ++k)

            dp[u][k] = max(dp[u][k],dp[v][k-1]);

    }

}

int main()

{

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

    for(int i=1;i<=n;i++)

    {

        int a;

        scanf("%d%d",&a,&val[i]);

        if(a)

          add(a,i);

        if(!a)add(0,i);

    }

    dfs(0,m);

    printf("%d",dp[0][m]);

}

Strategic game

这道题的意思是选择最少的点来覆盖一棵树，可以用最小点覆盖（也就是二分图最大匹配）或者树形\(dp\)来做，因为这里我们的专题是树形\(dp\)，所以我们现在就讲树形\(dp\)的做法。

我们做这道题的方法是用选择方程来做，因为你要做最小点覆盖，要么选这个点要么不选对吧。

于是\(dp\)的转移方程就是上述一方程

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<queue>

using namespace std;

int n;

struct edge

{

    int next,to;

} e[4000];

int head[4000],tot,dp[4000][2],ind[4000];

void add(int x,int y)

{

    e[++tot].next=head[x];

    head[x]=tot;

    e[tot].to=y;

}

void dfs(int x)

{

    dp[x][1]=1;

    for(int i=head[x]; i; i=e[i].next)

    {

        int v=e[i].to;

        dfs(v);

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

        dp[x][1]+=min(dp[v][0],dp[v][1]);

    }

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        memset(dp,0,sizeof(dp));

        memset(head,0,sizeof(head));

        memset(ind,0,sizeof(ind));

        tot=0;

        for(int j=1; j<=n; j++)

        {

            int a,b;

            scanf("%d:(%d)",&a,&b);

            for(int i=1; i<=b; i++)

            {

                int c;

                scanf("%d",&c);

                ind[c]++;

                add(a,c);

            }

        }

        int rt;

        for(int i=0; i<=n; i++)

            if(!ind[i])

            {

                rt=i;

                break;

            }

        dfs(rt);

        printf("%d\n",min(dp[rt][1],dp[rt][0]));

    }

}

巴特西

树形$dp$学习笔记