确实很浅
顾名思义，在树上进行的动态规划被称为树形DP，而且往往以一个点为根结点的子树所获得的最大收益为状态，通常从深到浅进行状态转移（树的深度） 例题： 1.最大独立子集 2.树的重心 3.树的直径
1.最大独立子集
Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。
输入格式 第一行一个整数N。(1≤N≤6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。
输出格式 第1行：输出最大的快乐指数。
样例 样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 样例输出 5
这是一道典型的最大独立子集问题，其中，子节点与父节点互斥（即取父节点就不能取任何一个子节点） 设dp[x][0]表示x号结点不参加宴会的最大快乐值，dp[x][1]表示参加 则
dp[x][0]=max(son[x][0],sonp[x][1]) dp[x][1]=max(son[x][0])+a[x]
code:
#include<cstdio> #include<iostream> using namespace std; int cnt,n,head[6005],dp[6005][2],a[6005],root,a1,a2; void read(int &x) { x=0; int f=1; char c=getchar(); while(c<'0'||c>'9') { if(c=='-') { f=-1; } c=getchar(); } while(c>='0'&&c<='9') { x=(x>>3)+(x>>1)+(c-'0'); c=getchar(); } x*=f; } struct ren{ int to,next,dis; }f[6005]; void add(int x,int y) { f[++cnt].to=y; f[cnt].next=head[x]; head[x]=cnt; } int max(int x,int y) { if(x>y) { return x; } return y; } bool vis[6005]; void d(int x) { dp[x][0]=0; dp[x][1]=a[x]; for(int i=head[x];i;i=f[i].next) { int v=f[i].to; d(v); dp[x][0]+=max(dp[v][0],dp[v][1]); dp[x][1]+=dp[v][0]; } } int main() { read(n); for(int i=1;i<=n;i++) { read(a[i]); } for(int i=1;i<n;i++) { int x,y; read(x); read(y); add(y,x); vis[x]=1; } for(int i=1;i<=n;i++) { if(!vis[i]) { root=i; break; } } d(root); printf("%d\n",max(dp[root][0],dp[root][1])); }2.树的重心 题目描述 树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后，树将分成两个连通块：（2,4,5），（3,6,7），则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，（4），（5），（1,3,6,7）最大的连通块包含4个节点；第一种方法可以得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。
输入格式 输入：第一行一个整数n，表示树的结点个数。（n<100）
接下来n-1行，每行两个数i，j。表示i和j有边相连。
输出格式 输出：第一行一个整数k，表示重心的个数。
接下来K行，每行一个整数，表示重心。按从小到大的顺序给出。
样例 样例输入 7 1 2 1 3 2 4 2 5 3 6 3 7 样例输出 1 1
树的重心的性质：删掉重心后任一联通块的结点数不超过n/2 初始每个点的值为1，每次递归当前节点的子节点，加上子节点个数。 如果子节点个数大于n/2，返回false 同样，因为是无向图，所以去掉重心后以重心的父节点为根的子树结点数也不能大于n/2 code:
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; int dis[1005],cnt,nn,n,head[1005],ans[1005]; bool vis[1005]; struct ren{ int to,next; }a[1005]; void add(int x,int y) { a[++cnt].to=y; a[cnt].next=head[x]; head[x]=cnt; } void dfs(int x) { bool flag=true; dis[x]=1; for(int i=head[x];i;i=a[i].next) { int v=a[i].to; if(vis[v]) { continue; } vis[v]=1; dfs(v); dis[x]+=dis[v]; if(dis[v]>n/2)//去掉中心后以子节点为根的子树节点数大于n/2 { flag=false; } } if(n-dis[x]>n/2)//另一部分大于n/2 { flag=false; } if(flag)//否则肯定是重心 { nn++; ans[nn]=x; } } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } vis[1]=1; dfs(1); printf("%d\n",nn); sort(ans+1,ans+1+nn); for(int i=1;i<=nn;i++) { printf("%d\n",ans[i]); } return 0; }3.树的直径 详见《算法竞赛进阶指南》 code:
#include <cstdio> #include <iostream> #include<cstring> using namespace std; int n, cnt, ans, head[1000005], dp[1000005]; bool vis[1000005]; struct ren { int to, next, dis; } a[1000005]; void add(int u, int v, int w) { a[++cnt].to = v; a[cnt].dis = w; a[cnt].next = head[u]; head[u] = cnt; } void dfs(int now) { vis[now] = 1; for (register int i = head[now]; i; i = a[i].next) { int v = a[i].to; if (vis[v]) { continue; } dfs(v); ans = max(ans, dp[v] + dp[now] + a[i].dis); dp[now] = max(dp[now], dp[v] + a[i].dis); } } int main() { scanf("%d", &n); for (register int i = 1; i < n; i++) { int x, y; scanf("%d%d", &x, &y); add(x, y, 1); add(y, x, 1); } dfs(1); printf("%d\n", ans); return 0; }