T1
破环为链，枚举区间。
接下来考虑本质不同的顺序只有：\(ABC\) 和 \(CBA\)，第二种可以通过序列逆序后重复操作得到。
接下来我们在枚举区间时，统计每一个元素在最后占区间中的每个字母出现次数。
我们发现交换有两种：一种是一次交换可以减少两个未匹配元素的，另一种则只可以减少一个。
贪心地，我们优先做第一种交换。
T2
问题转化为求最小点覆盖。
注意到当 \(m\) 和 \(k\) 的差很大时，如果存在答案，那么我们可以只选不超过 \(20\) 个点就可以，而且这些点一定是度数最大的几个。
所以我们每一次选当前度数最大的点，然后删去以它为端点的所有边。
当 \(m\) 和 \(k\) 的差比较小呢？直接二进制枚举即可。
T3
场上
会 \(k=1\) 的部分分。
考虑枚举在哪个村镇建，然后我们注意到最大距离一定是 \(\{A_0,A_n,B_0,B_n\}\) 中的两个点的最大距离。因为此时路径唯一，枚举计算即可。
也会 \(k=2\) 的部分分。
考虑枚举建路的点对，然后最大距离仍可能在上面集合的点对中得到，所有我们还是枚举然后计算距离，此时有的点对有两条路径，需要分别计算后取较小值。
对于环上的点，我们注意到它对答案的贡献不会超过环长的一半，滑动窗口求最大值即可。同时，因为它们位置的特殊性，我们也需要求它们到上述集合的点的距离。
T4
部分分神力。
我们先考虑 \(n \le 5000\) 的部分分。
一个很自然的思路，我们记 \(f_{i,j}\) 为已经处理了 \(i\) 的子树内的点，且 \(i\) 所在的链的链尾是 \(j\) 的最小代价；记 \(g_i=\min \limits_{j\in subtree(i)} f_{i,j}\)。
然后转移时就是枚举链尾，然后把其他子树的贡献加上即可。
再考虑菊花图的部分。
注意到此时状态数不多，可以沿用上述方法，只不过存储值是要用 unordered_map。
再考虑链的部分分。
我们充分发扬人类智慧，感觉决策点和当前位置不会隔太远，依据数学直觉，我们向后枚举 \(8000\) 个位置即可通过。
