洛谷9月月赛round1题解

前三题既然是原题题解就不发了。

对于T4：考虑如果u到v的路径的异或和为0，那么如果我们预处理每个点到根节点的异或和w[i]，那么必定有w[u]=w[v]。然后我们考虑倒过来做，把删边转换成加边。然后对于每个联通块维护一个数据结构，加边的时候直接乘法原理统计答案，然后启发式合并。如果是平衡树合并那么总的复杂度为nlog^2n，如果是线段树合并那么总的复杂度为nlogn，均可通过此题。