前言

考场做法，考场分数为 $97$，原因是先把所有奇偶性不同的点全修改了再整个跑了一次，实际上把最后一次修改反向作用在 $T'$ 上即可通过，不过由于我的写法不是很好改并且只有 $3$ 分所以去做 T3 了。

好像和官方题解的构造方法不太一样。

正文

大体思想

首先有一个结论就是，对于一对笔和橡皮，只有这一对笔和橡皮最后停留的两个点 $p_i,e_i$ 的度数奇偶性会反转，其他点的度数奇偶性不变。证明是显然的，不过考场上想要往这个方向想并不容易。

通过该结论考虑 $k$ 的下界，可以发现是 $\max(1,\frac{\sum\limits_{i=1}^n{[degT_i\bmod 2 \neq degT'_i\bmod2]}}{2})$。

我们尝试通过构造证明这个下界是可以取到的，构造算法分为两个部分，第一个部分是对 $\sum\limits_{i=1}^n{[degT_i\bmod 2 \neq degT'_i\bmod2]}=0$ 的构造，第二个部分是通过 $\frac{\sum\limits_{i=1}^n{[degT_i\bmod 2 \neq degT'_i\bmod2]}}{2}$ 次操作来变成第一种情况。

第一部分的构造

首先发现如果 $p_i,e_i$ 在同一个点，那么我们可以把它们都移动到任意相同点 $x$ 去，直接 $(x,x)$ 就好了。

然后注意到操作可逆，因此我们自然而然就能够想到让 $T$ 和 $T'$ 同时变为某个中间状态。

我们给出两个基本操作结构，便于后面的构造：

基本操作结构 $1$：

也就是把 $a-b,a-c,a-d$ 三条边，变成 $b-a,b-c,b-d$ 三条边。

操作方法就是先把 $p_i,e_i$ 都移动到 $d$，然后 $(b,a),(c,c)$ 即可。

基本操作结构 $2$：

也就是把 $a-b,c-d$ 两条边，变成 $a-c,b-d$ 两条边。

操作方法就是先把 $p_i,e_i$ 都移动到 $a$，然后 $(c,b),(b,c),(d,d)$ 即可。

有了上面两个基本操作结构之后，我们就可以开始构造了，先选定一个根 $rt$，满足这个根的度数为奇数（两棵树都选这个 $rt$ 为根）。

然后我们以 $T$ 为例，尝试把 $T$ 变成根下面挂了很多个叶子和至多一个不是叶子的儿子，这个不是叶子的儿子下面是一条链，这样的结构。

怎么做到这样的结构呢？我们先尝试让 $T$ 变成根下面挂若干条链。

从下往上考虑，对于一个 $x$，如果它此时已经是下面挂若干条链的结构了，那就把它的儿子通过基本操作结构 $1$ 尽可能接到父亲上面去，此时它会剩下至多一个儿子。所以当一个点的所有儿子都这样操作了之后，它自己也会变成一个点下面挂若干条链的结构，此处的操作次数是所有点的深度和，在随机树下是 $O(n\sqrt n)$ 的。

然后我们想要把所有的链合成一条，我们要解决的问题其实是形如 $a-b,a-c,c-d$ 的结构，我想要让它变成 $a-c,c-b,a-d$ 的结构，这样就可以让根的某个儿子吸收其他链除了叶子之外的所有点了（$a$ 这里是根）。然后我们就会发现，这其实就是基本操作结构 $2$，于是我们直接做 $O(n)$ 次基本操作结构 $2$ 就可以合并成一条大链了。

然后我们对 $T$ 也应用上面的步骤，此时 $T,T'$ 同构，我们只需要让链上顺序一致，并且让大链下方挂的叶子也是一致的，就可以了。

对于让大链下方挂的叶子一致这个问题，其实就是基本操作结构 $2$，因为我们是要把这个点和某个根的儿子（叶子）做交换。

而让大链顺序相等，容易发现，我们可以通过基本操作结构 $2$ 做到区间翻转，因此只需要 $O(n)$ 次操作即可实现排序。

至此，我们已经解决了第一部分的构造。

第二部分的构造

声明，此处并不考虑 $T$ 或者 $T'$ 为链的情况，因为原题保证数据随机，而题目中最小的测试点都有 $n=10$，所以我们可以认为随机到此种情况的概率极小，至少每个测试点十组数据不会出错。

基本操作结构 $3$：

这个操作是比较简单的，先移动到 $a$，然后 $(c,b)$ 即可，只是为了后面方便说明所以放在这里。

由于下界的分析部分，我们会发现我们只需要每次让一对（笔，橡皮）成功去掉两个度数奇偶性不同的点就可以了。

我们任意选两个奇偶性不同的点 $x,y$，如果它们都不是叶子，那就是很容易处理的，因为我们可以直接应用基本操作结构 $3$，来改变这两个点的奇偶性。

否则，由于先前的假设，我们可以认为 $x,y$ 的路径上一定存在至少一个度数 $\geq 3$ 的节点，我们找到这个节点，然后通过基本操作结构 $1$，来使得这个节点旁边挂着的子树，往 $x$ 或 $y$ 方向移动，从而使得 $x,y$ 中任意一个变得不是叶子，再应用基本操作结构 $3$ 即可。

此处由于数据随机，所以操作次数大概是 $O(n\sqrt n)$ 的（？

最后的优化

这样，我们就能够成功获得 $97$ 分了（CTS 评分标准），对于最后的操作，我们发现，只要我们把第二部分的构造的最后一次操作，反向应用到 $T'$ 上去，就可以实现把第一部分的构造和第二部分的构造的最后一次操作合并起来，只用同一对（笔，橡皮擦）。

如此即可获得 $100$ 分。