比赛链接

Solved by nikkukun.

给一个非负权的树，你可以任意加边或删边，但任意时刻要保证：

1. 连通
2. 任意环异或和为 $0$

求操作过后整棵树的最小权。

不难发现将边权往小修改的操作其实很像最小生成树的过程（接一个环，去掉环上的最大边），又发现这个图实际上一直是一棵生成树，其边权 $(u, v)$ 是原图中 $u \to v$ 的路径异或和，因此只要求这个图的 MST 即可。显然，令 $d(u)$ 为 $u$ 到根的路径异或和，则 $d(u) \oplus d(v)$ 就是 $u \to v$ 的路径异或和。

剩下的就是 老原题 了。考虑 Kruskal 过程从小到大连边：将所有 $d(i)$ 插入 trie 中，先给子树建好 MST，再往上合并两子树的 MST。合并的过程是要找两个子树中异或的最小值，这个可以暴力在两个子树中递归。由于每个节点只会被暴力搜到 $O(\log V)$ 次，因此总复杂度是正确的。如果不放心，也可以启发式合并维护一个子树的值，用另一个子树去查询最小值。

Solved by Potassium.

水题不表。

Solved by nikkukun.

水题不表。