长链剖分.
算法一
使用大力枚举,状态压缩等指数级别复杂度算法,期望得分 10 分.
算法二
设 f(i,j) 表示在子树 i 中选出一个联通块,必须包含 i ,并且这个联通块中最深的点到 i 的距离为 j 的方案数.
在树上 dfs ,不断将当前节点 u 的信息与它的儿子节点 v 的信息合并.
f(u,max枚举深度 i,j 时只需要枚举有用的,时间复杂度 O(n^2) ,期望得分 50 分.
算法三
对于 k=n-1 的部分,相当于没有联通块直径的限制,可以在算法二的基础上去掉第二维.
即设 f(i) 表示在子树 i 中选出一个联通块,且必须包含 i 的方案数.
时间复杂度 O(n) ,结合算法二,期望得分 60 分.
算法四
注意到算法二的 dp 第二维的下标是深度,可以利用长链剖分进行优化.
为了快速转移,需要给每个节点 i 开一棵线段树维护所有的 f(i,j) ,可以使用动态开点实现.
时间复杂度 O(n\log n) ,期望得分 100 分.
1 | //%std |
Gitalking ...