date: 2020-07-25 12:00~17:00

2020牛客暑期多校训练营（第五场）

题目大意：给你一棵带边权的树，你可以任意加边或删边，但是要保证每次操作后图连通、任意环的边权异或和为 $0$。求可能的最小边权和。

题解：设 $d[u]$ 为每个点到根的边权的异或和。每加一条边，边权只能是 $d[u]\oplus d[v]$。这样把它补成一个完全图，由于每个欧拉子图都可以被 cycle basis 表示，因而仍然是合法的。显然不论如何加边和删边，所得的图都是该完全图的生成子图。因而原问题就是求它的最小生成树。

考虑 kruskal，首先将所有相同的 $d[u]$ 合并，然后把 $d[u]$ 插入 trie，显然每棵子树内部会完全合并，因而对于一个点的两棵子树，只会找最小的异或和合并一次。那么对于左子树的每个点在右子树中查询一次即可，每个点只会问 $\log$ 次。

时间复杂度 $\mathcal{O}(n\log^{2}A)$。