树型动态规划和状态压缩动态规划
树型动态规划是动态规划的一种特殊形式，它将问题分解成许多子问题，每个子问题都是一个树形结构。树型动态规划的关键是将问题分解成小规模的子问题，并使用 memoization 或 tabulation 保存中间结果，以避免重复计算。
树型动态规划的必要条件是子树之间不能相互干扰。如果子树之间存在相互干扰的关系，那么需要添加变量以使它们不相互干扰。
在树型动态规划中，DP 数组的定义是 dp[i][0] 表示不选择第 i 个节点时，节点 i 及其子树能选出的最多人数，dp[i][1] 表示选择第 i 个节点时，节点 i 及其子树的最多人数。
状态转移方程是：
- 对于叶子节点，dp[k][0] = 0, dp[k][1] = 1
- 对于非叶子节点 i，dp[i][0] = ∑max(dp[j][0], dp[j][1]) (j 是 i 的儿子)
- dp[i][1] = 1 + ∑dp[j][0] (j 是 i 的儿子)
最多人数即为 max(dp[0][0], dp[0][1])
在判断最优解是否唯一时，可以新加一个状态 dup[i][j]，表示相应的 dp[i][j] 是是否是唯一方案。
对于叶子结点，dup[k][0] = dup[k][1] = 1。对于非叶子结点，可以使用以下规则来判断：
- 对于 i 的任一儿子 j，若 dp[j][0] > dp[j][1] 且 dup[j][0] == 0) 或 dp[j][0] < dp[j][1] 且 dup[j][1] == 0) 或 dp[j][0] == dp[j][1]，则 dup[i][0] = 0
- 对于 i 的任一儿子 j，有 dup[j][0] = 0, 则 dup[i][1] = 0
树型动态规划的应用非常广泛，例如在关系树中选择一部分人，使得每个人之间不能有直接的上下级关系。树型动态规划可以解决这类问题，并且可以判断最优解是否唯一。
状态压缩动态规划是动态规划的一种特殊形式，它将问题分解成许多子问题，每个子问题都是一个状态压缩的形式。状态压缩动态规划的关键是将问题分解成小规模的子问题，并使用 bit manipulation 保存中间结果，以避免重复计算。
状态压缩动态规划的应用非常广泛，例如在游戏中判断某个状态是否存在某个子状态。状态压缩动态规划可以解决这类问题，并且可以判断最优解是否唯一。
在实际应用中，树型动态规划和状态压缩动态规划可以结合使用，以解决更加复杂的问题。例如，在游戏中判断某个状态是否存在某个子状态，并且需要选择一部分人，使得每个人之间不能有直接的上下级关系。树型动态规划和状态压缩动态规划可以结合使用，以解决这类问题，并且可以判断最优解是否唯一。
树型动态规划和状态压缩动态规划是动态规划的两种特殊形式，它们可以解决许多实际问题，并且可以判断最优解是否唯一。
