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的方法去分
代码在链接中有，就不贴了，学习到了
查看15道真题和解析
投递美团等公司10个岗位