观前须知:本文顺序较为混乱，根据本人复习顺序写的，难度严格不递增

dp不像数据结构可以套路性的将，以例题为主吧

part 1:树形dp

树是一种非常好的结构，其天然的递归形态保证了最优子结构，使得dp有很好的发挥空间

一般状态与子树和路径有关，也有时扯到叶子节点，所以不套路化，特殊情况可能会一大把

下文记 \(W(u,v)\) 表示 \(u\) 和 \(v\) 之间的边权，单独写 \(W(u)\) 表示(有根树中)和父亲的连边长

\(son(x)\) 表示 \(x\) 的所有儿子组成集合，\(fa(x)\) 表示 \(x\) 的父节点

由于树天生的递归式结构，树形dp很难表现为递推的形式，通常表现为dfs

没有上司的舞会

给出一个 \(n\) 个节点的树，点有点权 \(A_x\)，选出若干不直接相连的点使得点权最大化

不妨设 \(f_{i,j}\) (\(j=1/2\))，表示子树 \(i\) 中选与不选的最大答案

转移:\(f_{i,1}=A_i+\sum\limits_{v\in son(i)}f_{v,0}\)，就是考虑选这个点后把所有子节点不选的值加上再加自己点权

\(f_{i,0}= \sum\limits_{v\in son(i)}\max(f_{v,0},f_{v,1})\) 反正自己不选，子节点随便选

由于dfs的回溯结构会在回溯时转移回根

时空 \(O(n)\)

Tree

求直径长度及数量

通常树形dp同时涉及值和数量需要开两个数组或者像上一题开个二维

记录两个变量 \(ans,cnt\) 表示长度和数量

设 \(f(i)\) 表示子树 \(i\) 内一端是 \(i\) 的最长链，\(g(i)\) 为数量，\(c(i)\) 记录当前的 \(f(i)\) 是由哪个子树转移过来的

考虑转移，父亲的 \(f(i)\) 一定是一个儿子的加上儿子到爹地的边权

$f(i)=\max\limits_{v\in son(i)}(f(v)+w_{i,v}) $

回溯时我们分两次更新：

先尝试用当前的 \(f(x)+\) 当前搜的儿子的 \(f+W(son)\) 更新答案，如果大于， $cnt=g[x]*g[son] $，等于 \(cnt+=g[x]*g[son]\)

然后类似的用儿子的 \(f+W(son)\) 更新 \(f(x),g(x)\)，这样是不会重复计数的，因为前后你找的直径必定是本质不同的

...吧