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)$

求直径长度及数量

通常树形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)$，这样是不会重复计数的，因为前后你找的直径必定是本质不同的

...吧

重学OI#4 简单dp