树形DP概念和实例讲解

94119 阅读 0 评论 0 点赞

一、什么是树型动态规划

顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：

（1）叶－>根：在回溯的时候从叶子节点往上更新信息

（2）根 - >叶：往往是在从叶往根dfs一遍之后（相当于预处理），再重新往下获取最后的答案。

不管是从叶－>根还是从根 - >叶，两者都是根据需要采用，没有好坏高低之分。

树形DP的难点有什么？

（1）和线性动态规划相比，树形DP往往是要利用递归的，所以对递归不熟悉的同学，是一道小小的障碍，说是小小的，因为要去理解也不难。

（2）细节多，较为复杂的树形DP，从子树，从父亲，从兄弟……已经一些小的要处理的地方，脑子不清晰的时候做起来颇为恶心

（3）状态表示和转移方程，也是真正难的地方。做到后面，树形DP的老套路都也就那么多，难的还是怎么能想出转移方程，状压DP、概率DP这些特别的DP应该说做到最后都是这样！

建有向图还是无向图？一般来说我们做树DP都是从上往下递归，如果不乱搞是不会从子节点往根节点的遍历的，这时候可以建有向图，只加边一次就可以，对于有“思想洁癖”的人来说，如果加一次边就可以再让他加两次是很难受的。但是有些题目可能很隐蔽的某个地方涉及到从子节点往上访问，就会错的很惨。所以，一般不非常确定建有向图就可的话还是建无向图吧。

做树形dp常用的两种方法：

（1）由子节点来更新父节点；

（2）由父节点来更新子节点。

二、例题解析

例题1：树的直径（树中最远两点的距离）:

思路：对每个点来说，求出以它为父节点，路径的最大值和次大值

代码：

#include<bits/stdc++.h>
 
using namespace std;
 
const int N=2e4+10;
 
int e[N],ne[N],w[N],h[N],idx;
int f1[N],f2[N];//f1[i]表示父节点为i的最远距离,f2[i]表示次远距离
 
void add(int a,int b,int c)
{
    e[idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx++;
}
 
void dfs(int u,int fa)
{
    //f1[u]=0,f2[u]=0;
    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        dfs(j,u);
        int d=f1[j]+w[i];
        if(d>f1[u]){
            f2[u]=f1[u];
            f1[u]=d;
        }
        else if(d>f2[u]){
            f2[u]=d;
        }
    }
}
signed main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,-1);
    
    int ans=-1e9;
    for(int i=1;i<=n;i++){
        ans=max(ans,f1[i]+f2[i]);
    }
    cout<<ans<<endl;
    return 0;
}

例题2：树的中心（以某个点为中心，其到其他点的最大值最小，则该点为中心）

思路：我们可以像例1一样，例1是以1为根，来找最长路径，我们可以把每个点都当作一次根，都做一次遍历，来求最长路径，然后取min即是答案，但这样会超时，因此考虑换个思路。

（1）对每个节点，其到其他点最大值为max(向下到其儿子最远点，向上的最远点），这里前一个很好求，即例1中的f1[i], 而对第二个要进行讨论。

（2）对于向上的最远点有两种情况：向上走就是求一个点的父节点的不走该节点的最长路径，其实我们知道了每一个节点向下走的长度就可以知道向上的最长路径了，一个子节点 j 的向上最长路径就是它的父节点 u 的最长向上路径和最长向下路径取最大值，如果向下最长路径经过了 j 就改为第二长的向下路径，对应代码：

if(p1[u]==j)up[j]=max(up[u],d2[u])+w[i];
else up[j]=max(up[u],d1[u])+w[i];

此做两次树形DP即可

#include<bits/stdc++.h>
 
using namespace std;
 
const int N=2e4+10;
 
int e[N],ne[N],h[N],w[N],idx;
 
int f1[N],p1[N],f2[N];//p[i]记录最长路径是由哪个子节点转移过来的
int up[N];//向上走的最大值
 
void add(int a,int b,int c)
{
    e[idx]=b; ne[idx]=h[a] ; w[idx]=c ; h[a]=idx++;
}
 
void dfs1(int u,int fa)
{
    f1[u]=f2[u]=0;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        dfs1(j,u);
        int d=f1[j]+w[i];
        if(d>f1[u]){
            f2[u]=f1[u];
            f1[u]=d;
            p1[u]=j;//记录最长路径由哪个儿子转移来的
        }
        else if(d>f2[u]) f2[u]=d;
    }
}
 
void dfs2(int u,int fa)
{
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(j==fa) continue;
        if(p1[u]==j)//说明向上走的最大路径经过该儿子节点
        {
            up[j]=max(up[u],f2[u])+w[i];
        }
        else up[j]=max(up[u],f1[u])+w[i];
 
        dfs2(j,u);//注意这里是由父节点更新子节点
                  //因此要先更新信息在递归处理,与dfs1不同
    }
}
signed main()
{
    int n;
    cin>>n;
    memset(h,-1,sizeof h);
 
    for(int i=1;i<=n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dfs1(1,-1);//由子节点更新父节点
    dfs2(1,-1);//由父节点更新子节点
    int ans=1e9;
    for(int i=1;i<=n;i++){
        ans=min(ans,max(f1[i],up[i]));
    }
    cout<<ans<<endl;
    return 0;
}