前言

树形dp是一种在树上做的dp，通常的结构为：

void dp(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        dfs(v);
        update(f[u],f[v]);  //用f[v]来更新f[u]
    }
}

先递归子节点，再从子节点向上转移，这样就是一般的树形dp。

树直径

考虑这样一道题：
给定一棵无根树，求两个距离最远的节点间的距离，两个相邻结点距离为1。
首先，两个距离最远的结点必定是“边界点”，即度为1的点。
我们不妨对于每个点，求出这个点到这个点的子树的所有边界点的最长距离与次长距离，设为f[x][1],f[x][2]，那么答案也就自然是$\max_{1\leq i\leq n}(f[i][1]+f[i][2])$
主要的瓶颈就在于：如何求出每个点的f呢？
我们看下dp代码

void dfs(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int y=to[i];
        if(v[y])    //已经访问过了（即父节点），跳过
          continue;
        dfs(y); //递归子节点
        //以下代码请好好斟酌
        if(h[u][1]<=h[y][1]+1) {    //如果最长路可以更新
            h[u][2]=h[u][1];    //将次长路更新为最长路
            h[u][1]=h[y][1]+1;  //将最长路更新为新值
        }
        else if(h[u][2]<=h[y][1]+1) //如果次长路可以更新
          h[u][2]=h[y][1]+1;    //更新次长路
    }
}

因为这个树是一个无根树，所以我们从任意一个点开始执行dfs都可以。

树上背包问题

CTSC1997 选课

题目链接：选课或acwing286
这n门课构成了一个森林的结构，为了简便，可以添加零号节点为各个树根的父亲，方便dp。
状态定义：f[u][t]表示在以u为根的子树中选t门的最高得分。
状态的转移实际上是一个分组背包模型，一个点的所有子节点看做是一组物品v，每组物品有f[v][i]的价值与i的消费。每组物品中只能取一个。

#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
int score[N];
int f[N][N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}


void dp(int u) {
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        dp(v);
        for(int t=m;t>=0;t--)   //背包状态转移
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j]+f[v][j]);
    }
    if(u!=0)
      for(int i=m;i>0;i--)
        f[u][i]=f[u][i-1]+score[u];
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        int u;
        cin>>u>>score[i];
        add(u,i);
    }
    dp(0);
    cout<<f[0][m];
    return 0;
}

二叉苹果树

题目链接：二叉苹果树
有了上面一道题，这道题就更加简单了，直接看代码。
注意不同的是，这道题是边权，上一题是点权。

#include <iostream>
#include <cstring>

using namespace std;
const int N=3e2+5;
int n,m;
int head[N],to[N],val[N],nxt[N],cnt;
bool vis[N];
int f[N][N];

void add(int u,int v,int w) {
    to[++cnt]=v;
    val[cnt]=w;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dp(int u) {
    vis[u]=true;
    f[u][0]=0;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i],w=val[i];
        if(vis[v])
          continue;
        dp(v);
        for(int t=m;t>=0;t--)
          for(int j=t;j>=0;j--)
            f[u][t]=max(f[u][t],f[u][t-j-1]+f[v][j]+w); //此处减一是要把自己算上去
    }
}

int main() {
    memset(f,0xc0,sizeof(f));
    cin>>n>>m;
    for(int i=1;i<n;i++) {
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    dp(1);
    cout<<f[1][m];
    return 0;
}

典型树形dp

没有上司的舞会

题目链接：没有上司的舞会或acwing285
状态定义：f[u][0]表示当u不选时，u的子树的最大值，f[u][1]表示选u时，u的最大值。
那么很容易写出状态转移方程了。

#include <iostream>
#include <cstdio>

using namespace std;
const int N=2e4+5;
int head[N],nxt[N],to[N],cnt;
int f[N][2],h[N],n,root,in[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

void dp(int p) {
    f[p][0]=0;
    f[p][1]=h[p];
    for(int i=head[p];i;i=nxt[i]) {
        int y=to[i];
        dp(y);  //这边要注意：如果有明确的依赖关系，就不需要判断是否为父亲，建边时建单向边即可。但是如果只是说有一条边，那么就要双向建边，并判断到达点是否为当前点的父亲
        f[p][0]+=max(f[y][1],f[y][0]);  //如果当前点不选，它的下级既可以选也可以不选
        f[p][1]+=f[y][0];   //如果当前点选，那么只有不选它的下级
    }
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
      cin>>h[i];
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        add(v,u);
        in[u]++;    //记录入度，根的入度必定为0
    }
    for(int i=1;i<=n;i++)
      if(in[i]==0) {
        root=i;
        break;
      }
    dp(root);   //从根开始dp
    cout<<max(f[root][0],f[root][1]);   //选根与不选根取最大值
    return 0;
}

数字转换

题目链接：数字转换
看起来不像树形dp，但我们可以把它转化成数形dp
设一个数x的约数和叫d[x]，那么对于每个x我们不妨看做是x到d[x]连一条边。最后求这棵树的直径就行了。

#include <iostream>
#include <cstdio>

using namespace std;
const int N=4e5+5;
int n,m;
int head[N],to[N],nxt[N],cnt;
bool v[N];
int h[N][3],ans;
int sum[N];

void add(int u,int v) {
    to[++cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

//求直径传统艺能
void dfs(int u) {
    v[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int y=to[i];
        if(v[y]) 
          continue;
        dfs(y);
        if(h[u][1]<=h[y][1]+1) {
            h[u][2]=h[u][1];
            h[u][1]=h[y][1]+1;
        }
        else if(h[u][2]<=h[y][1]+1)
          h[u][2]=h[y][1]+1; 
    }
}

int main() {
    cin>>n;
    //求每个数的约数和并加边
    for(int i=1;i<=n;i++) { //枚举因子来求约数和
        if(sum[i]<i) {  //约数和小于原数
            add(i,sum[i]);  //加两条边
            add(sum[i],i);
        }
        for(int j=i*2;j<=n;j+=i)    //枚举i的倍数
          sum[j]+=i;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
      ans=max(ans,h[i][1]+h[i][2]); //直径
    cout<<ans;
    return 0;
}

二次扫描与换根法

如果题目中要对每个点都进行统计，并且这棵树是无根树，那么就可以使用这个方法。
1、第一次扫描，任选一个点为根，执行从下到上的dp
2、第二次扫描，以刚才那个点为根，进行从上到下的推导
我们可以解决比如：求每个点到任意点的最长路，或者次长路等的问题。

Accumulation Degree

这道题目蓝书上面有讲解，就不赘述了。