叠甲:也有可能是我智商不够没看懂,有没有大爷教我正确的思路?
题解给出的结论是:
度数 ≥3 的点为关键点,关键点之间是一条度数均为 2 的长链,假设两关键点之间链长(包含关键点)为 c,两个关键点上挂的子树(包含关键点)大小为 a,b,有 (a−1)+(b−1)+c=n,当 k<(a−1)+(b−1) 时:

(图示中最右侧两个关键点满足条件,但红蓝无法交换)
-
题解 1:左右子树的点就可以任意交换。不能解释图示情况
-
题解 2:一定可以交换链两端的点(但我觉得他应该暗含了要求中间链上均为空,但这个题解写的太简略了完全不明所以)
-
题解 3:链上的任意两个点之间都是可以交换的,这说明只要能移动到这条链上的点都是可互相交换的(不能解释图示情况)
-
题解 4:能到达左端的牛和能到达右端的牛一定可以交换(不能解释图示情况)
此外,如果将牛看成置换,没有题解说明为什么等价类一定可以由若干对换作用得到,换句话说,为什么不存在形如《可以将三个牛的位置循环移位,但这三个牛的位置不能两两任意交换》这类情况。我认为比较合理的说明是交换位置只能在度数 ≥3 的地方交换(但这个解释还是有些毛估估感觉)