每次交换两个鞋，求相邻两个配对且左鞋子在左边的最小操作次数。

贪心。

每只和最前面的配对，求个逆序对就可以了。

给定一棵有边权的树，求 $\max\limits_{1\le i<j\le n}\operatorname{dis}(i,j)$，其中，$\operatorname{dis}(i,j)$ 指树上 $i$ 到 $j$ 的路径上边权异或和。

发现 $\operatorname{dis}$ 与根无关，所以指定 $1$ 为根。

令 $a_i$ 为 $\operatorname{dis}(1,i)$，显然，用一遍 DFS 可以处理出。

我们发现：

于是，把 $a_i$ 丢到 01Trie 上去求最大异或对即可。