我们考虑设 f_u 表示以 u 为根的子树的答案，我们发现将 u 和子节点 v 合并不好转移，一般在处理异或运算发现不好转移的时候我们都会想到拆位，所以我们可以对 u 所在的连通块拉出来单独拆位，也就是记 g_{u, i, 0/1} 表示以 u 所在连通块二进制第 i 位是 0/1 时，其他连通块的总贡献。这样设状态的好处是我们可以单独考虑 u 所在的连通块对 f_u 的贡献，不难得到 f_u = \sum_{i} 2^ig_{u, i, 1}。
接下来考虑如何转移，考虑新加进一个儿子 v，那么我们可以选择把 u \to v 割掉，也可以把 v 所在的二进制下第 i 位为 0/1 的连通块拼进来，不难得到
g_{u, i, 0} \gets g_{u, i, 0}\cdot f_v + g_{u, i, 1} \cdot g_{v, i, 1} + g_{u, i, 0} \cdot g_{v, i, 0}
g_{u, i, 1} \gets g_{u, i, 1}\cdot f_v + g_{u, i, 1} \cdot g_{v, i, 0} + g_{u, i, 0} \cdot g_{v, i, 1}