LGR-164-Div.2

发布时间 2023-10-15 19:54:23作者: 音街ウナ

B

考虑我们实际上仅仅在钦定 \((u,v)\) 不切断时需要通过 \(v\) 所在子树的异或和这个 状态 来更新 \(u\) 对应异或和的状态,此时状态内每一位都是独立的。所以直接拆位仍然能够转移,得到 \(f_{i,j,0/1}\) 表示节点 \(i\) 子树内第 \(j\) 位异或和确定情况下的答案。

而在钦定 \((u,v)\) 切断时,根本不管 \(v\) 子树内的信息。于是直接设 \(g_i=\sum_j f_{i,j}\),直接通过 \(g_v\) 转移到 \(f_{u,j,a_u \operatorname{and} 2^j}\) 即可。