略
—我不懂他咋贪心的–dalao能讲讲吗
没想到能遇见comet oj的群友
… …为啥认识我鸭
…一个月前的题目了–
没办法,你太活跃了的说
hhh那确实
你的id是?
伤翎.
哦哦哦,记得
蒟蒻居然会被记得!感动.jpg
毕竟当初私聊过吧hhh
自己的一点拙见:这个贪心题,不要被树节点的顺序套进去。对于一个给定的树,染色方法是唯一的,先每次找到均值最大的节点,然后和其父节点合并,不需要理会根节点,直接合并 n - 1 次,最后肯定会合并为一个点,而且这个点必定为根节点。 为什么一定到最后的时候,权值最大的点一定是根节点呢?因为合并的过程总是“自下而上”的合并。也就是说既然父节点染色后才能染色子节点,那么就逆向思维,先把最大的子节点染色,然后立马染色父节点,直到最后一直向上合并到父节点。 好了,现在我们把刚才的过程全部逆推,那么逆推的过程就是从“根节点” 开始染色的过程,也就是最优解的染色路径了。
感谢提点
—我不懂他咋贪心的–dalao能讲讲吗
没想到能遇见comet oj的群友
… …为啥认识我鸭
…一个月前的题目了–
没办法,你太活跃了的说
hhh那确实
你的id是?
伤翎.
哦哦哦,记得
蒟蒻居然会被记得!感动.jpg
毕竟当初私聊过吧hhh
自己的一点拙见:这个贪心题,不要被树节点的顺序套进去。对于一个给定的树,染色方法是唯一的,先每次找到均值最大的节点,然后和其父节点合并,不需要理会根节点,直接合并 n - 1 次,最后肯定会合并为一个点,而且这个点必定为根节点。
为什么一定到最后的时候,权值最大的点一定是根节点呢?因为合并的过程总是“自下而上”的合并。也就是说既然父节点染色后才能染色子节点,那么就逆向思维,先把最大的子节点染色,然后立马染色父节点,直到最后一直向上合并到父节点。 好了,现在我们把刚才的过程全部逆推,那么逆推的过程就是从“根节点” 开始染色的过程,也就是最优解的染色路径了。
感谢提点