题目分析

我们需要将树上的 N 个顶点（N 为偶数）两两配对，使得所有配对顶点间路径上边权异或和的总和最小。

---

核心思路

1. 问题转化

设 a[u] 为从根节点到节点 u 的路径上所有边权的异或和。那么任意两点 u, v 之间的路径异或和就是 a[u] ^ a[v]。

因此问题转化为：给定数组 a[1..N]，将其分成 N/2 对，使得每对异或值之和最小。

---

2. 算法设计

2.1 按位分治

代码采用按位分治策略，从高位到低位处理：

• 对于当前位 de，将所有点分为两组：

  • b：该位为 0 的点
  • c：该位为 1 的点

• 如果两组大小都是偶数，直接递归处理

• 如果两组大小都是奇数，需要将一个点从一组移到另一组

2.2 关键函数

solve(vector<pii> a, int de)

计算最小总异或和，其中 a 是 (value, index) 对的列表。

基本情况处理：

• 当 de < 0 或点集很小（2 或 4 个点）时直接计算

递归过程：

1. 按当前位分组
2. 如果两组大小都是偶数，分别递归
3. 如果都是奇数，尝试移动一个点，选择最优方案

print(vector<pii> a, int de)

根据 solve 的计算结果构造具体的配对方案。

---

3. 优化技巧

3.1 记忆化

map<vector<pii>, int> mp[25];

存储每个位深度和点集对应的最优移动选择。

3.2 局部搜索

TTT 函数通过交换配对中的顶点来进一步优化：

• 两对交换：检查是否可以通过交换顶点降低总成本
• 三对交换：更复杂的局部优化

3.3 随机化

使用 shuffle 和多次运行来避免陷入局部最优。

---

4. 算法流程

1. 预处理：DFS 计算每个节点到根的路径异或和 a[i]
2. 分治求解：调用 solve 计算最小总成本
3. 构造解：调用 print 生成配对方案
4. 局部优化：多次运行 TTT 进行局部搜索
5. 输出：最终的总成本和配对方案

---

复杂度分析

• 预处理：O(N)
• 分治求解：最坏 O(2^N)，但通过剪枝和记忆化实际运行良好
• 局部优化：O(N³) 但常数较小

对于 N ≤ 200 在实际中可接受。

---

样例验证

样例 1

输入：
6
5 2 42
5 4 52
6 3 26
4 6 39
1 6 15

输出：
54
1 6
3 5
4 2

验证：配对成本 = (a₁^a₆) + (a₃^a₅) + (a₄^a₂) = 54

样例 2

输入：
4
1 2 4
3 4 5
2 3 1

输出：
1
2 3
1 4

验证：配对成本 = (a₂^a₃) + (a₁^a₄) = 1

---

算法标签

• 分治 (Divide and Conquer)
• 异或技巧 (XOR Techniques)
• 局部搜索 (Local Search)
• 记忆化 (Memoization)
• 树上前缀和 (Tree Prefix Sum)

---

总结

本题通过将树上的路径异或和转化为数组元素配对问题，利用按位分治策略和局部搜索优化，在合理时间内找到接近最优的配对方案。核心在于发现路径异或和可以表示为节点值的异或，以及通过位运算性质进行高效分治。