一、什么是樹型動態(tài)規(guī)劃 

顧名思義，樹型動態(tài)規(guī)劃就是在“樹”的數(shù)據(jù)結(jié)構(gòu)上的動態(tài)規(guī)劃，平時作的動態(tài)規(guī)劃都是線性的或者是建立在圖上的，線性的動態(tài)規(guī)劃有二種方向既向前和向后，相應(yīng)的線性的動態(tài)規(guī)劃有二種方法既順推與逆推，而樹型動態(tài)規(guī)劃是建立在樹上的，所以也相應(yīng)的有二個方向： 

（1）葉－>根：在回溯的時候從葉子節(jié)點往上更新信息

（2）根 - >葉：往往是在從葉往根dfs一遍之后（相當(dāng)于預(yù)處理），再重新往下獲取最后的答案。

不管是 從葉－>根 還是 從 根 - >葉，兩者都是根據(jù)需要采用，沒有好壞高低之分。

樹形DP的難點有什么？

（1）和線性動態(tài)規(guī)劃相比，樹形DP往往是要利用遞歸的，所以對遞歸不熟悉的同學(xué)，是一道小小的障礙，說是小小的，因為要去理解也不難。

（2）細節(jié)多，較為復(fù)雜的樹形DP，從子樹，從父親，從兄弟……已經(jīng)一些小的要處理的地方，腦子不清晰的時候做起來頗為惡心

（3）狀態(tài)表示和轉(zhuǎn)移方程，也是真正難的地方。做到后面，樹形DP的老套路都也就那么多，難的還是怎么能想出轉(zhuǎn)移方程，狀壓DP、概率DP這些特別的DP應(yīng)該說做到最后都是這樣！

建有向圖還是無向圖？ 一般來說我們做樹DP都是從上往下遞歸，如果不亂搞是不會從子節(jié)點往根節(jié)點的遍歷的，這時候可以建有向圖，只加邊一次就可以，對于有“思想潔癖”的人來說，如果加一次邊就可以再讓他加兩次是很難受的。但是有些題目可能很隱蔽的某個地方涉及到從子節(jié)點往上訪問，就會錯的很慘。所以，一般不非常確定建有向圖就可的話還是建無向圖吧。

做樹形dp常用的兩種方法：

（1）由子節(jié)點來更新父節(jié)點；

（2）由父節(jié)點來更新子節(jié)點。

二、例題解析

例題1：樹的直徑 （樹中最遠兩點的距離）:

思路：對每個點來說，求出以它為父節(jié)點，路徑的最大值和次大值

代碼：

#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]表示父節(jié)點為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為根，來找最長路徑，我們可以把每個點都當(dāng)作一次根，都做一次遍歷，來求最長路徑，然后取min即是答案，但這樣會超時，因此考慮換個思路。

（1）對每個節(jié)點，其到其他點最大值為max(向下到其兒子最遠點，向上的最遠點），這里前一個很好求，即例1中的f1[i], 而對第二個要進行討論。

（2）對于向上的最遠點有兩種情況：向上走就是求一個點的父節(jié)點的不走該節(jié)點的最長路徑，其實我們知道了每一個節(jié)點向下走的長度就可以知道向上的最長路徑了，一個子節(jié)點 j 的向上最長路徑就是 它的父節(jié)點 u 的最長向上路徑和最長向下路徑取最大值，如果向下最長路徑經(jīng)過了 j 就改為第二長的向下路徑，對應(yīng)代碼：

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]記錄最長路徑是由哪個子節(jié)點轉(zhuǎn)移過來的
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;//記錄最長路徑由哪個兒子轉(zhuǎn)移來的
        }
        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)//說明向上走的最大路徑經(jīng)過該兒子節(jié)點
        {
            up[j]=max(up[u],f2[u])+w[i];
        }
        else up[j]=max(up[u],f1[u])+w[i];
 
        dfs2(j,u);//注意這里是由父節(jié)點更新子節(jié)點
                  //因此要先更新信息在遞歸處理,與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);//由子節(jié)點更新父節(jié)點
    dfs2(1,-1);//由父節(jié)點更新子節(jié)點
    int ans=1e9;
    for(int i=1;i<=n;i++){
        ans=min(ans,max(f1[i],up[i]));
    }
    cout<<ans<<endl;
    return 0;
}