首页 > 其他分享 >CCPC Qinhuangdao 2020 K, Kingdom's Power做题思路

CCPC Qinhuangdao 2020 K, Kingdom's Power做题思路

时间:2022-08-30 19:11:35浏览次数:49  
标签:Kingdom Power 步数 兄弟 做题 推过来 节点

首先,对于一个子树,我们显然只有两种去让军队走过他的办法,一种是从兄弟节点调一些军队来,另一种是从根节点推过来。

感觉有一个结论,就是我这个位置如果用兄弟节点推过来的只是因为兄弟节点推过来的步数小于从根节点重新来一个步数小。

我们首先会遇到一个问题,如果现在兄弟节点推过来的确实比从根来小,但是有没有可能这个给其他兄弟节点更优一点呢?这是不可能的。

image

蓝色的线与红色的线都是选择,会发现他们所需要的步数其实是一样的。

同时,我们可以想到的一点是,我们应该按照节点的深度来排序操作,因为每个军队如果停下来的话他肯定停在叶子节点。从小到大的排序每个节点。

标签:Kingdom,Power,步数,兄弟,做题,推过来,节点
From: https://www.cnblogs.com/Mercury-City/p/16640509.html

相关文章