CF2134
D
当一个操作对数据结构的影响难以刻画，而题目要求我们通过该操作将数据结构调整到特定的状态（接受状态）时，可以尝试找到数据结构的某个特征，刻画操作对特征的影响考虑。应保证接受状态的该特征是同一的。
回到该题，我们选择特征为 树的直径。发现一次操作至多使直径增大 \(1\)。
证明：一次操作后，任意两点之间的距离至多增加 \(1\)。
而这样的操作对于任意非链的树都是容易构造的。同时，链（即接受状态）的直径（特征）都为 \(n\)。
当一个操作对数据结构的影响难以刻画，而题目要求我们通过该操作将数据结构调整到特定的状态（接受状态）时，可以尝试找到数据结构的某个特征，刻画操作对特征的影响考虑。应保证接受状态的该特征是同一的。
回到该题，我们选择特征为 树的直径。发现一次操作至多使直径增大 \(1\)。
证明：一次操作后，任意两点之间的距离至多增加 \(1\)。
而这样的操作对于任意非链的树都是容易构造的。同时，链（即接受状态）的直径（特征）都为 \(n\)。