模板及讲解
树上背包
问题：给$n$个物品，物品之间有依赖关系，每个物品有重量$w_i$和价值$v_i$，求取物品的最大价值。
解：给定的是一个森林，我们要把森林的根节点全部连到$0$号节点，然后树形DP，设$dp(u, i)$为以$u$为根的子树必选$u$选$i$重量的物品时的最大价值，那么$dp(u, i) = dp(u, i-j) + dp(v, j)$，之后因为要必选$u$，所以大于$w_u$的$i$的$dp(u, i) = dp(u, i-w_u) + v_u$，小于$w_u$的$i$的$dp(u,i) = 0$.
树的重心(质心)
问题：求出一棵无根树的某个点，使得这个点当做根以后最大子树的节点数最小
解：求出每棵树的子树节点数$siz_u$，每个节点作为根时深度$blc=max(siz_v, n-siz_u)$，$v \in son(u)$,然后答案就是$min(blc)$
性质：
1把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。(用于合并信息的性质)
2把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离
3去掉任意一个重心后，生成的各个块的节点数的最大值一定小于等于原树的节点数除以2。
4以一棵树的重心为根的子树的节点个数，一定大于等于该树节点总数的一半。
5在一棵树的所有子树中，找到某一子树，使得其节点数恰好大于等于原树节点总数一半，那么该子树的根一定是一个重心。(如果该节点不是重心，也就是把它去掉后产生的连通块中至少有一个节点个数大于原树节点个数的一半。)
45互逆
树的直径(最长路径, 最远点对)
问题：求出树上最长的一条链
解：两次 BFS。第一次随便找一个点 BFS 找到离这个点最远的那个点$u$，用$u$继续 BFS 找离这个点最远的那个点$v$，则链$uv$为树的直径
性质(直径常用反证矛盾法)：
1距离树上任意节点最远的点 一定是树点直径的两个端点之一
2以树的直径中点上的一点为根，将这颗无根树转化为有根树的话，这样做会使树的深度最小，且为树的直径的一半（向上取整）(因为如果有一个叶子节点比直径更深的话，那么就可以构成一个更长的直径，与假设矛盾。)
3所有直径的中心相同，这个中心可以是一个顶点，也可以在一条边上。所有点到他的最远点都要通过这个中心
4树的直径的端点必然是他的子树直径的端点(用于合并信息的性质)
5有两棵树，如果把它们随意连一条边，会变成一棵树，新树的直径的端点一定是之前两棵树的直径的共4个端点的两个
树的最大独立集
问题：
解：
环套树DP
基本思路：
1、有可能是断环边后树处理：Bzoj 1040，NOIP2018Day2T1
2、有可能是找到唯一环后将这个环作为一个广义根，然后再结合环一起计算：Bzoj 1791
问题1：给定$n$个点，$n$条边，保证任意两点间至少存在一条路径。其中每个点均有其权值$v_i$，问如何选择点，使得在保证任意直接相连的两点不会同时被选中的情况下，被选中的点的权值和最大？
解：对于一棵$n$个节点的树，必然有$n-1$条边，对于一个$n$个点$n$条边构成环的图，我们可以断开这条使得树变成环的边，然后用树形DP设$dp(u,0)$为以$u$为根的子树的最大权和并且不能选$u$, $dp(u,0)$为以$u$为根的子树的最大权和并且必选$u$。然后就对这条边的两个顶点进行两次树形DP，答案就是$max(dp(u, 0), dp(v, 0))$。(第一个是第一次DP的结果，第二个是第二次DP的结果)。为什么要进行两次DP呢，因为如果我们只DP$u$，那么选$u$的方案就不能得到(如果取01最大值，那样会有可能$u, v$同选，不满足题意)，就会漏解。
注意以下数据：
常见题型
1、常规树形DP
Q: 在树上的DP。
解: 通常用dfs完成，从叶子推到根。
例题: Bzoj 1369
2、树上背包
Q: 见讲解
解: 见讲解
例题: Bzoj 2427
3、求树的重心
Q: 见讲解
解: 见讲解
例题: Poj 1655
4、求树的直径
Q: 见讲解
解: 见讲解
例题:
5、求树的最大独立集
Q: 见讲解
解: 见讲解
例题:
6、环套树DP(标志：$n$个点$n$条边)
Q: 见讲解
解: 见讲解
例题: Bzoj 1040
7、树上选点覆盖
Q: Bzoj 1596
解:$f(u, 0)$为不在$u$建基站，$u$与$u$的子树都有信号。$f(u, 1)$为在$u$建基站，$u$与$u$的子树都有信号。$f(u, 2)$为不在$u$建基站，$u$没有信号，$u$的子树都有信号。
例题: Bzoj 1596
