笔记 - 树形DP
-
有限电视网 背包类树形DP
-
选课 典 分组背包类树形DP
-
数字转换模板 树的最长链
-
没有上司的舞会模板 树形DP
-
旅行机器人难 树形DP+换根 or 特殊性质秒题
-
树典 难 树形DP+二分优化+蜜汁参数
\(题意\) 求最多能在树上找出多少条长度均为 k 的互不相交的路径, 其中 \(k\in [1, n]\)简解
-
\(O(N)\) DP 求当 长度为K时的最大路径数
\(f[u]\): 子树中完整的链的个数
\(g[u]\): 以u及u子树中的某个点为端点的最长链
贪心的计算 \(f[u]\): 若最长与次长之和大于等于 K, 立即f[u]++, g[u]=0
同时注意 次长路径的判断 -
\(O(???)\) 二分优化
发现当 K 越大, 连续相等的答案便越多, 可以二分(以 \(sqrt(n)+?\)为分界点)
-