做题记录 25.10.21

szt100309 · 2025-10-21 21:00:45 · 个人记录

\textcolor{black}\odot CF1305G Kuroni and Antihype

新增点 0，(x,y) 之间的边权改为 a_x+a_y，最终答案减去 \sum a_i，显然不变

显然 a_x\&a_y=0 时 a_x+a_y=a_x\oplus a_y

考虑 \text{Kruskal} 算法，从大到小枚举 s=a_x\oplus a_y，然后枚举 a_x，用并查集维护即可

时间复杂度 O(3^L\alpha(2^L))，其中 L=\log_2 V，注意特殊处理重复的数值

代码

参考