一句话理解
树上最大独立集：选出最多点，两两不相邻。
为什么要学
树形 DP 模板。
讲解
f[u][1]=1+∑f[v][0]，f[u][0]=∑max(f[v][0],f[v][1])。
例子
叶子很好算，往上合并。
常见错误
- 权值不是 1 时忘加权。
- 输出方案没记转移。
第 349 课
树上最大独立集
🟠 进阶 约 10 分钟
练习 做完再看下一课
独立集中任意两点都不能有边相连。
进度保存在本机浏览器里。
左右方向键也可翻课
第 349 课
树上最大独立集：选出最多点，两两不相邻。
树形 DP 模板。
f[u][1]=1+∑f[v][0]，f[u][0]=∑max(f[v][0],f[v][1])。
叶子很好算，往上合并。
独立集中任意两点都不能有边相连。
左右方向键也可翻课