选定一个阈值 B。对于使用人数 \le B 的编程语言（不妨认为出现了 c 次），枚举团队领导 u，再暴力枚举其他使用该编程语言的人对应的结点，如果该结点本来不在 u 子树内并且 u 子树内对应深度有“空位”（即可以与其交换，并使答案增大的结点），那么对其进行一次操作，使其进入 u 的子树内。处理子树内空位数量可以对于每个深度预处理出所有的点的 dfs 序，子树查就变成了区间查，直接 lower_bound 就可以了。这一部分的时间复杂度为 O(c^2\log c)。
讲义中提到了直接构造的做法。一种比较直观的想法是：一圈一圈往里绕，但是如果有点在角上那么段数可能达到 2n；如果 x_i=y_i=i，则应当从左下开始依次经过每个点。将两种想法结合，维护三个序列 a,b,c，依次对应绕圈，左上-右下、左下-右上。四步为一轮，依次选择当前 x 最小，y 最小，x 最大，y 最大的点。若某次选择点之后发现无法与上一个点衔接，则说明一个点在角上，可以将其放入 b 和 c 中，依次访问三个序列，总共需要 (n+3) 条线段。
若 u 在两棵树中均为叶子，则交换对应的边并删除 u 即可递归子问题。否则不妨设 \deg_1(u)=1 且 \deg_2(u)=2，令 (u,a)\in T_1 且 (u,b),(u,c)\in T_2，且 T_2 中 (u,b) 在 u\to a 的简单路径上。在 T_1 与 T_2 中将 u 删除，并向 T_2 中加入边 (b,c)，递归子问题。在子问题的解决中，必有一步交换 (b,c),(d,e)，将这一步扩展为：交换 (u,a),(u,b)，交换 (u,c),(d,e) 即可得到原问题的解。
直接暴力做，时间复杂度 O(n^2)。
Day 4
考试日。
Day 5
试题题解
更新一下昨天的试题题解。
T1 猫粮（catfood）
以下将优质猫粮记为 A，普通猫粮记为 B。
注意到只有 2n 个猫粮，而猫有 n 个，又因为每个猫至少要吃两个猫粮，所以每个猫正好会吃两个。就变成了匹配问题。
考虑 AB 先匹配，然后 AA 匹配（如果剩余的 A 有奇数个考虑补一个进去，以下不妨设 A 个数为偶数；如果 A 的个数为 2，那么只要满足 a_1+a_2=m 即可；否则需要满足 m\bmod 2=0 \land \forall i,a_i=\frac{m}{2}），最后还要判 BB 是否能匹配（不判这个只有 95 分）。