登录以参加训练计划

树形 DP 入门题：

利用树形 DP 得到子树的信息。

1. 最大独立集
2. 最少边覆盖
3. 最少点覆盖
4. 树上背包（点权）
5. 树上背包（边权）
6. 树上背包（子树约束 优化 时间复杂度 $O(n^3)$ -> $O(n^2)$）
7. 树上背包（深度约束 优化 空间复杂度 $O(n*other)$ -> $O(Depth*other)$）
8. 树上背包（长链剖分 优化 时空复杂度 $O(n^2)$ -> $O(n)$）
9. 习题：树上背包 + 组合数 求方案

换根 DP 入门题：

在树形 DP 的基础上进行二次树形 DP，通过子树的信息将子树之外的信息计算得出。

1. 维护边权信息
2. 维护点权信息
3. 习题：同时维护点权和边权信息
4. 习题：换根 DP 经典题（树上 K 近权和）
5. 习题：2024 年百度之星省赛（第三场）银牌题

基环树 DP 入门题：

通常是多个基环树（仅包含一个环联通图），也称作基环树森林。需要对每个基环树以环上点为树根进行树形 DP，再在环上利用环上子树的信息进行线性 DP。

1. 基环树的直径
2. 基环树的最大独立集（2025 年浙江省赛专科组金牌题）
3. 习题：基环树的最大独立集（变种）