题解：动态维护树上异或值计数

问题转化

给定一棵 $n$ 个节点的树，每个节点有权值 $v_i$（$0 \le v_i < m$，$m$ 是 $2$ 的幂且 $m \le 128$）。
定义一棵连通子树的价值为子树中所有节点权值的异或和。
支持两种操作：

1. 修改单个节点的权值
2. 查询价值为 $k$ 的非空连通子树个数

答案对 $10007$ 取模。

关键性质

$m$ 是 $2$ 的幂，$m \le 128$，所以权值范围很小，可以用异或卷积处理。

树形 DP

设 $f_u[x]$ 表示以 $u$ 为根的子树中，包含 $u$ 且价值为 $x$ 的连通子树个数。
设 $g_u[x]$ 表示以 $u$ 为根的子树中，不要求包含 $u$（即可以包含 $u$ 的子树的某个连通块）且价值为 $x$ 的连通子树个数。

初始化：$f_u[v_u] = 1$（只有 $u$ 自己），$g_u$ 初始全 $0$。

转移：考虑 $u$ 的一个子节点 $v$，已经合并了前若干个子树的 $f_u, g_u$，现在加入子树 $v$。

新的 $f_u'$ 由两部分组成：

1. 不含 $v$ 子树：$f_u$
2. 包含 $v$ 子树：$f_u$ 和 $f_v$ 的异或卷积（因为 $u$ 必须选，$v$ 子树也必须包含 $v$）

具体来说： 令 $h = f_u \otimes f_v$（异或卷积），则 $f_u'[x] = f_u[x] + \sum_{a \oplus b = x} f_u[a] \times f_v[b]$。

但注意：$f_u$ 和 $f_v$ 卷积表示 $u$ 所在的连通块和 $v$ 所在的连通块合并（通过边 $(u,v)$ 连接），形成新的连通块，价值为两者异或。

因此：

$$f_u' = f_u + (f_u \otimes f_v)$$

这里 $\otimes$ 是异或卷积。

对于 $g_u$：

1. 不含 $v$ 子树：$g_u$
2. 包含 $v$ 子树：$g_v$
3. $f_u$ 和 $f_v$ 卷积后得到的新连通块也贡献给 $g_u$（因为这些连通块在 $u$ 的子树内） 但 $g_u$ 实际上表示整个已合并子树中的答案，所以：

$$g_u' = g_u + g_v + (f_u \otimes f_v)$$

最终对于整棵树（任选根，比如 $1$），所有价值为 $k$ 的连通子树个数就是 $g_{root}[k]$。

异或卷积优化

由于 $m \le 128$，可以直接 $O(m^2)$ 卷积，但 $n \le 30000$，总复杂度 $O(n m^2)$ 过大。

利用 Fast Walsh-Hadamard Transform (FWHT) 优化异或卷积到 $O(m \log m)$。

对于两个数组 $A,B$ 长度 $m$（$m$ 是 $2$ 的幂），FWHT 可以在 $O(m \log m)$ 时间内计算 $C = A \otimes B$。

步骤：

1. 对 $A,B$ 做 FWHT 变换得 $\hat{A}, \hat{B}$
2. $\hat{C}[i] = \hat{A}[i] \times \hat{B}[i]$
3. 对 $\hat{C}$ 做逆 FWHT 得 $C$

由于模数 $10007$ 很小，直接整数运算即可。

动态 DP

问题在于有修改操作，需要动态维护 $f_u, g_u$。

使用 动态 DP 技巧，将树剖分成重链，对每条重链用线段树维护矩阵乘积。

定义状态向量 $F_u = (f_u, g_u, 1)$，其中 $f_u, g_u$ 是长度为 $m$ 的数组，$1$ 是常数 $1$。

转移可以写成矩阵形式： 设 $u$ 有轻儿子 $v_1,\dots,v_t$，重儿子 $son$。 令 $LF_u = f_u$ 仅考虑轻儿子的贡献（即 $f_u$ 初始为 $[v_u]$，然后与所有轻儿子的 $f_v$ 卷积）。 类似定义 $LG_u = g_u$ 仅考虑轻儿子的贡献。

则 $F_u$ 可以由 $F_{son}$ 通过一个转移矩阵得到：

$$\begin{bmatrix} f_u \\ g_u \\ 1 \end{bmatrix} = \begin{bmatrix} LF_u \otimes f_{son} & 0 & LF_u \\ LG_u + g_{son} + (LF_u \otimes f_{son}) & 1 & LG_u \\ 0 & 0 & 1 \end{bmatrix} \times \begin{bmatrix} f_{son} \\ g_{son} \\ 1 \end{bmatrix} $$

实际上更精确的： $f_u = LF_u + (LF_u \otimes f_{son})$（注意这里 $LF_u$ 是已经包含 $u$ 和轻儿子的基础数组） $g_u = LG_u + g_{son} + (LF_u \otimes f_{son})$

因此转移矩阵 $M_u$ 作用在 $(f_{son}, g_{son}, 1)$ 上得到 $(f_u, g_u, 1)$。

由于 $f_u, g_u$ 是数组，矩阵的每个元素是一个线性变换（即对数组的卷积或加法）。

简化：标量化

由于 $m \le 128$，我们可以将数组视为向量，转移矩阵就是 $2m+1$ 维的矩阵，但矩阵乘法复杂度 $O(m^3)$ 不可接受。

更好的方法：直接在线段树节点维护 $f$ 和 $g$ 数组，合并时用 FWHT 卷积。

重链剖分 + 线段树

对每个节点 $u$，预处理：

• $lf_u$：$u$ 与所有轻儿子卷积后的 $f$ 数组（初始为 $[v_u]$）
• $lg_u$：$u$ 的所有轻儿子的 $g$ 之和

对于重链，从叶子到根用线段树维护合并： 线段树节点 $[l,r]$ 存储：

• $f$：该区间节点组成的连通块（包含 top）的 $f$ 数组
• $g$：该区间内的总答案

合并两个相邻区间 $[l,mid]$ 和 $[mid+1,r]$： 设左区间对应节点 $u$（深度较小），右区间对应其重儿子链。 合并方式与 DP 转移相同： $f_{new} = f_u + (f_u \otimes f_{son})$ $g_{new} = g_u + g_{son} + (f_u \otimes f_{son})$

这样，线段树根节点存储的就是整条重链的答案。

对于整棵树，从根开始，依次合并每条重链。

修改操作

修改节点 $x$ 的权值：

1. 更新 $x$ 的 $lf_x$（因为 $v_x$ 变了）
2. 更新 $x$ 所在重链的线段树
3. 由于 $x$ 的 $lf$ 改变，会影响其父节点的 $lf$（如果 $x$ 是父节点的轻儿子）
4. 不断向上跳重链，更新受影响链的线段树

每次更新复杂度 $O(\log n \times m \log m)$。

查询操作

查询价值为 $k$ 的连通子树个数： 整棵树的答案存储在根所在重链的线段树根节点的 $g$ 数组中，直接输出 $g_{root}[k] \bmod 10007$。

初始化

先 DFS 预处理每个节点的 $lf, lg$，然后对每条重链建线段树。

算法步骤

1. 读入 $n, m, v[],$ 边，建树。
2. 树链剖分，得到重儿子、top 等。
3. DFS 计算每个节点的 $lf, lg$：
   • $lf_u$ 初始为只有 $v_u$ 的数组（即 $lf_u[v_u]=1$）
   • $lg_u$ 初始全 $0$
   • 对每个轻儿子 $v$： $lf_u = lf_u + (lf_u \otimes f_v)$（这里 $f_v$ 是 $v$ 为根的子树答案，需要递归计算） $lg_u = lg_u + g_v$
   • 计算 $f_u, g_u$（暂时用于初始化）
4. 对每条重链建线段树，每个叶子节点对应一个节点 $u$，存储 $(lf_u, lg_u)$。 线段树合并时使用 FWHT 卷积。
5. 处理操作：
   • Change x y： a. 更新 $v_x = y$ b. 重新计算 $x$ 的 $lf_x$（初始化为 $[y]$，然后与所有轻儿子的 $f$ 卷积） c. 更新 $x$ 所在重链的线段树 d. 设 $p$ 为 $x$ 的父节点，若 $x$ 是 $p$ 的轻儿子，则更新 $p$ 的 $lf_p$（需要除去旧的 $f_x$ 贡献，加入新的 $f_x$ 贡献） 由于模数小，无法直接除法，可以用“减-加”方式：$lf_p = lf_p - (lf_p \otimes old\_f_x) + (lf_p \otimes new\_f_x)$ 但注意这是卷积操作，不能简单加减。实际需要重新计算 $p$ 的所有轻儿子的贡献。 简单做法：记录 $p$ 的所有轻儿子列表，重新卷积。 e. 重复向上更新直到根。
   • Query k： 输出 $g_{root}[k] \bmod 10007$
6. 所有操作结果对 $10007$ 取模。

复杂度

• 预处理：$O(n m \log m)$
• 修改：$O(\log n \times m \log m \times$ 轻儿子数$)$，轻儿子数均摊 $O(\log n)$
• 查询：$O(1)$

由于 $m \le 128$，可过。