关于造数据

回复帖子

@OIforJoy 2020-05-27 15:28 回复

一般来说一个正解复杂度为线性的树形DP想卡掉带log的做法数据出多少比较合适?担心因为常数开1e7会T...

用于PPT讲知识点用QAQ

@FZzzz 2020-05-27 15:38 回复 举报

如果是 dfs 序上建树状数组这种 log 可能得 5e6?

@FZzzz 2020-05-27 15:39 回复 举报

当然你要是只是讲题的话你可以直接说“要求线性复杂度”

@OIforJoy 2020-05-27 16:16 回复 举报

@FZzzz 5e6容易让正解挂掉...我这个需要预处理中心(直径的中点或中间的边的2个端点)然后换根再dfs预处理至少3个信息还要把直径抠出来然后还要跑一遍树上DP以及再次dfs离线求和n同阶次的树上k级祖先...

@FZzzz 2020-05-27 16:23 回复 举报

因为你这个常数的话不好卡,然后因为有个 k 级祖先所以你卡 1log 也没啥意思

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。