树型dp套路

4.2 2分
image.png

总结

image.png

二叉树节点间最大距离

image.png

  • 思路 可以用x这个节点 参不参与最大距离的计算 分类讨论
  1. 如果x不参与计算 那么 最大距离是 左子树上最大的距离 或 右子树上最大的距离
  2. 如果x参与计算 那么最大距离是 左子树上最远的点 经过x节点 到右子树上最远的点 也就是子树高度+1
  3. 需要管子树要的信息 一个是高度 一个是子树最大距离

image.png

派对的最大快乐值

4.2 35分讲完了
image.png

  • 根据x节点参不参加聚会进行分类讨论 如果x节点参加聚会 那么最大快乐值 只能是 x快乐值加上所有直接下级不来的最大快乐值
  • 如果x节点不参加聚会 那么 x为根的树的最大快乐值 为 0 + 每个直接下级员工的最大快乐值，其中每个员工可以分为来或不来的最大快乐值

image.png

mirrors遍历

4.2 43分