引用博客：
https://blog.csdn.net/dcx2001/article/details/78269908
https://www.cnblogs.com/ifmyt/p/9588872.html
树形dp一般f[i][j]，i表示以i为根的树，
基本方程：
选择结点类：f【i】【0】=f【j】【1】
f【i】【1】=max/min（f【j】【0】，f【j】【1】）
树形背包：f[v][k]=f[u][k]+val
f[u][k]=max(f[u][k],f[v][k−1])
别的就是具体分析，一般都是f【i】【j】（大部分不超过二维，第一维通常代表根节点。）
一、子树型
给一棵 n 个点的树，以 1 号点为根，求以每个点为根的子树大小
P1122 最大子树和
https://www.luogu.com.cn/problem/P1122
则f[i]表示，以i为根节点的子树最大权值和 。
#include<bits/stdc++.h> using namespace std; const int maxn=200000; int n,a[maxn],head[maxn],cnt,f[maxn]; struct edge{ int nx,to,w; }edge[maxn*2]; void add(int u,int v) { edge[++cnt].nx=head[u]; edge[cnt].to=v; head[u]=cnt; } void dfs(int u,int fa) { f[u]=a[u]; for(int i=head[u];i;i=edge[i].nx) { int v=edge[i].to; if(v!=fa) { dfs(v,u); f[u]+=max(0,f[v]); } } } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<n;i++) { int u,v; cin>>u>>v; add(u,v),add(v,u); } dfs(1,0); int ans=-1000000; for(int i=1;i<=n;i++) ans=max(ans,f[i]); cout<<ans; }
P2016 战略游戏
https://www.luogu.com.cn/problem/P2016
在节点上放士兵，所以考虑单个结点是否放置；
则f[i][0/1]代表是否放置。对于一个节点，所受影响的就是子结点（采用从叶子点枚举）；
#include<bits/stdc++.h> using namespace std; const int maxn=200000; int n,a[maxn],head[maxn],cnt,f[maxn][2]; struct edge{ int nx,to,w; }edge[maxn*2]; void add(int u,int v) { edge[++cnt].nx=head[u]; edge[cnt].to=v; head[u]=cnt; } void dfs(int u,int fa) { f[u][1]=1,f[u][0]=0;//初始化，只考虑本节点，放置为1，不放为0 for(int i=head[u];i;i=edge[i].nx) { int v=edge[i].to; if(v!=fa) { dfs(v,u); f[u][0]+=f[v][1];//如果当前节点不放士兵，子结点一定放 f[u][1]+=min(f[v][0],f[v][1]);//如果当前节点放置，后面结点无所谓 } } } int main() { cin>>n; for(int i=1;i<=n;i++) { int u,k; cin>>u>>k; for(int j=1;j<=k;j++) { int v; cin>>v; add(u,v),add(v,u); } } dfs(0,-1); cout<<min(f[0][1],f[0][0]); }
树上背包：
这类问题就是让你求在树上选一些点满足价值最大的问题，一般都可以设f[i][j]表示i这颗子树选j个点的最优解。
P2014 [CTSC1997]选课
https://www.luogu.com.cn/problem/P2014
题目描写很清楚，与背包有关；树上背包；
借鉴博客：https://www.cnblogs.com/ifmyt/p/9588872.html
基本代码：
void dfs(int u,int tot) { //f[i][j]表示以i为根节点，选择j个子结点的最优值 for(int i=head[u];i;i=edge[i].nx) { int v=edge[i].to; for(int j=0;j<tot;j++) f[v][j]=f[u][j]+val[u];
dfs(v,tot-1); for(int j=1;j<=tot;j++) f[u][j]=max(f[u][j],f[v][j-1]); } }
原文：https://www.cnblogs.com/Showend/p/12958047.html