学习自 这里

可以想到看成有根树之后,设 \(f(i,j)\) 表示 以 \(i\) 为根的子树,权值异或和为 \(j\) 的方案数。合并两个子树的 \(f\) 就是异或卷积,设 \(F_i=f(i,*)\) ,则 \[ F_i=x^{v_i}*\prod (F_{ch(i)}+x^0) \] 为了统计答案,设 \(h(i,j)=\sum_{k \in tree(i)} f(k,j)\) ,能维护 \(h\) 就能询问了。设 \(H_i=h(i,*)\) ,有 \[ H_i=F_i+\sum H_{ch(i)} \] 考虑如何实现修改单点权,快速维护这些信息。

这里有一种方法,就是所谓基于变换合并的树上动态 DP 的链分治算法 定义 \[ LF_i=\prod_{ch(i)\neq hvy(i)}(F_{ch(i)}+x^0) ,\quad LH_i=\sum_{ch(i)\neq hvy(i)} H_{ch(i)} \] 那么 \[ F_i=x^{v_i}*LF_{i}*(F_{hvy(i)}+x^0), \quad H_i=F_i+H_{hvy(i)}+LH_{i} \] 考虑当我们改变一个点 \(i\) 的点权后,其 \(F_i,H_i\) 都改变了,然后沿重链往上一个个更新。 接下来就是个很妙的想法,注意到这个更新的过程可以看作一个线性变换。即 \((F_{hvy(i)},H_{hvy(i)},x^0)\to (F_i,H_i,x^0)\) 。转移矩阵: \[ T=\begin{pmatrix} LF_{i}* {x^{v_i}} & LF_{i}* {x^{v_i}} & 0 \\ 0 & 1 & 0 \\ LF_{i}* {x^{v_i}} & LF_{i}* {x^{v_i}} + LH_i & 1 \end{pmatrix} \] 那么就解决了,我们只需要用线段树实现修改某个矩阵,查询矩阵的乘积就好啦。当然我们不需要每次做卷积都 \(FWT\) ,可以一开始就把所有都 \(FWT\) ,然后运算时直接点乘,最后输出逆回来就好了。

还可以减小一下常数,注意到

\[ \begin{pmatrix} a_0 & a_1 & 0 \\ 0 & 1 & 0 \\ a_2 & a_3 & 1 \\ \end{pmatrix} * \begin{pmatrix} b_0 & b_1 & 0 \\ 0 & 1 & 0 \\ b_2 & b_3 & 1 \\ \end{pmatrix} = \begin{pmatrix} a_0b_0 & a_0b_1+a_1 & 0 \\ 0 & 1 & 0 \\ a_2b_0+b_2 & a_2b_1+a_3+b_3 & 1 \\ \end{pmatrix} \]

所以实际实现时只需要存 \(4\) 个值, 常数变小很多。