求问本题结论证明
查看原帖
求问本题结论证明
105254
Piwry楼主2021/5/29 10:57

具体来说:

设原树重心度数为三。以重心为根,记 p1,p2,p3p_1, p_2, p_3 为重心的三个儿子

考虑一种算法,它每次取和上次取的结点不在同一个 p1,p2p_1, p_2p3p_3 子树内的最深的结点,将该结点删去(如果是第一次取就没有不同子树的限制)

记初始时 p1,p2,p3p_1, p_2, p_3 子树的大小为 a,b,ca, b, c,且为了讨论方便设 abca\geq b\geq c。当满足 a<b+ca < b+c 时,上述算法一定会在某一时刻满足,一颗子树(p1,p2,p3p_1, p_2, p_3 之一)的大小为另两颗子树大小的和

2021/5/29 10:57
加载中...