📜 WAYPOINT LESSON
Checkpoint — In/Out Tree DP
⭐ beginner⏳ 30 min read📍 Lesson 141 of 281
Weighted independent set on a 2·10^5-node caterpillar; the conflict-ignoring DP that lets adjacent nodes both be taken is the graded wrong answer.
Checkpoint — Tree DP. Cây n = 200 000 đỉnh: dòng 2 là cha của 2..n, dòng 3 là giá trị val[1..n] (có thể âm). In tổng lớn nhất của tập độc lập trọng số (tập rỗng hợp lệ). DP lấy/bỏ hậu thứ tự; bản gãy cho phép hai đỉnh kề cùng lấy — in ra tổng mọi giá trị.