题解

Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined) G

若干个联通块直接把每个联通块的答案加起来，因此只考虑一个联通块的情况，设点数为$all$。
考虑求出联通块中的简单环，注意并不是真的要求出所有的简单环（这是NP的），只要满足求出的简单环足够能通过异或构成所有的简单环即可。
怎么求呢，考虑任意一棵生成树的那些返祖边，每一条返祖边对应一个简单环，而且这些环足够通过异或构成所有简单环了。
现在考虑两点间的路径，我们可以任选一条路径，然后将路径异或上若干的简单环变成任意的一条其他的路径，原因很简单，考虑任意一棵生成树上的路径，假如此时要走一条返祖边，那么将原路径异或上返祖边对应的环即可。
因此两点间所有路径可以看成生成树上的路径异或上若干个简单环，求出简单环异或值的线性基，设线性基为$b _ {1\sim cnt}$，设$un = b _ 1 | b _ 2 | ... | b _ {cnt}$。
现在我们根据二进制位来考虑对答案的贡献，对于$2 ^ i$，假如$2 ^ i \in un$，那么对于任意一对$(u,v)$，无论其生成树上路径异或值中是否包括$2 ^ i$，都可以通过调整某一个线性基来实现这一位为$1$，因此这里对答案的贡献就是：

$$2 ^ i\cdot \frac{all(all - 1)}{2}\cdot 2 ^ {cnt - 1}$$
如果$2 ^ i\not \in un$，我们需要考虑树上路径中这一位异或值为$1$的条数。考虑记录树根到所有点的路径异或值，记录这一位有$1$的条数$c$，那么条数就是$c(all - c)$，因此这里的贡献就是：
$$2 ^ i\cdot c(all - c) \cdot 2 ^ {cnt}$$
这样我们就能够在$O(n\log 10^{18})$的时间内求出答案。