树形 DP - 最大独立集

来源：基础算法精讲 by 灵茶山艾府

视频精讲：树形 DP - 最大独立集

题意与示例

337. 打家劫舍 III

题目链接：房屋组成二叉树且不能同时偷直接相连的房屋，求最大金额。

示例：输入 root = [3,2,3,null,3,null,1]，输出 7。

1377. T 秒后青蛙的位置

题目链接：青蛙从节点 1 出发，每秒等概率跳向未访问邻点，求 t 秒后位于 target 的概率。

示例：输入 n = 7, edges = [[1,2],[1,3],[1,7],[2,4],[2,6],[3,5]], t = 2, target = 4，输出 1/6。

2646. 最小化旅行的价格总和

题目链接：可预先把若干互不相邻节点的价格减半，求所有树上旅行路径的最小总价。

示例：输入 n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]，输出 23。