codeforces 348B B. Apple Tree(dfs+数论)

这个题我一开始是当作树形dp搞的

题解:戳我


其实树上的dfs想成了树形dp,也是没走太多弯路的

但是为什么处理错了?


因为维护的方向和数值不对


维护的方向应该是从父亲的方向推到儿子的方向,但是基本树形dp都是从儿子维护到父亲


想想:如果当前节点u,有三个孩子,每个孩子有a1,a2,a3个孩子,那么如果我想要最小删除,那么当前节点u的总价值必须怎么计算?

应该是lcm(a1,a2,a3)对吧,我算成了a1*a2*a3


所以整理完毕思路之后:

叶子节点是可以放着不用管的

对于每个非叶子节点,我们都需要求个lcm,然后维护一下

如果当前的值不够分,那么就需要把所有的值全部删除(这样每个子树都是0,才可以)

否则,就按照整除lcm的方法去分


代码在链接中有,就不贴了,学习到了

全部评论

相关推荐

06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
05-26 10:24
门头沟学院 Java
qq乃乃好喝到咩噗茶:其实是对的,线上面试容易被人当野怪刷了
找工作时遇到的神仙HR
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务