题目给出一棵树。第\(i\)步拆的一定是第\(i\)层与第\(i+1\)层之间的连边，否则不是最优（自行证明即可），所以可以暴力枚举每一次拆哪一个节点与上一个节点的连边。

把所有节点所在的层数存下来，一号点在第\(1\)层，枚举每一层的每个节点（由于\(1\)号节点已经被感染，从第二层开始搜索就可以了）

大概可分为以下几步：

存好一整棵树

把每一层的节点都存在一个数组里面

标记以ii号节点为根节点的子树的节点个数

标记与回溯

暴力搜索

关于多叉树的存储，这里介绍一种简单有效的方法。考虑如下代码：

\(tree[i]\)存\(i\)号节点的所有信息：

\(father\)存父亲(在这题没有用) ； \(child[]\)存它所有的孩子 ； \(child[0]\)是它孩子的个数。

由于数据范围很小，我们不用担心造成空间过多的浪费。

结构体构建完成之后，我们就可以在读入的同时把整棵树存好。

如果能够理解，标记深度是比较简单的。

如图：我们令\(1\)号节点的深度为\(1\) ； 则\(2,3\)节点深度为\(2\) ； \(4,5,6,7\)节点的深度为\(3\)； \(8\)节点的深度为\(4\)。这棵树一共有\(4\)层。

代码用\(deep[i][j]\)存第\(i\)层第\(j\)个节点的编号。\(deep[i][0]\)是第\(i\)层一共的节点数。