利用广度优先搜索树(bfs树)的两个性质。本质跟上面的解是一样的,个人觉得思路更自然一些。
1. bfs树中,每个节点的深度等于它到根的最短距离
2. 所有图中的边(u,v),在bfs树中u,v的深度至多差1
对这个题,就是把bfs树同一深度的点看作一个集合,深度为0(根)的点数记为a0,深度为1的集合的点数记为a1,……依此类推。
由性质2立即可得a0+a1>=8, a2+a3+a4>=8, ……, a23+a24+a25>=8, a27+a28>=8 。a26>=1。
经过简单的计算立即可得矛盾,故不存在深度为28的节点。
深度为27的构造利用上面的这组式子的取等条件即可。