PDD 一面

树形 DP 问题描述 树形动态规划是指在树结构上进行状态转移的问题。 常见的有树的最大独立集、树的直径等。 通常需要定义状态表示树上某个节点的最优解。 树的最大独立集 算法思想 定义dp[i][0/1]表示以i为根的子树中，不选/选择i节点的最大独立集大小 如果选择当前节点，则子节点不能选 状态转移方程： dp[i][0] = sum(max(dp[j][0], dp[j][1])) 其中j是i的子节点 dp[i][1] = 1 + sum(dp[j][0]) 其中j是i的子节点 最终答案为max(dp[root][0], dp[root][1]) 代码实现 c++ java...