本来该有一期如何用 Static Top Tree + 二进制分组虚树 + 分散层叠 + Finger Search 击落数字树暴力的，大概是我上了无数个火箭毛毛虫使得朴素的 $\mathcal{O}(nd^2)$ 暴力优化到了 $\mathcal{O}(n\log^2(n)\alpha(n)$，但是太难写了而且一定跑不过，我们就不管它了

事实上本题可以做到空间 $\mathcal{O}(n)$。

首先我们需要抛弃读完题就想到的维护连通块的思路，不然没法在这个题做到优秀的复杂度，接下来我们打开题解读到这样一个性质：

定义函数 $f(u)$：

• 当 $u$ 不是叶子： $f(u)=f(l_u)\oplus f(r_u)$，其中 $l_u,r_u$ 为 $u$ 的两个儿子，$\oplus$ 表示集合对称差；
• 当 $u$ 是叶子：若 $u$ 有颜色 $c$ 则 $f(u)=\{c\}$，否则 $f(u)=\emptyset$。

记 $c=\operatorname{card}\left(\{f(u)\mid u\in V,\,\lvert f(u)\rvert\geq 2\}\right)$，则询问的答案为 $2^{2n-1-c}$。

这个的原因是先随便取出来一组方案，一些 $f(u)$ 相等的结点一定处于某一条路径上（因为路径的交是路径，$f(u)$ 相等的点一定是某些路径的交的子集），如果 $\lvert f(u)\rvert\geq 2$ 的话你需要确保它们只有偶数个被翻转了，因此方案数除以 $2$，而对于 $\lvert f(u)\rvert\leq 1$ 的结点你对它们是否翻转是无限制的。

那我把集合看作 $0,1$ 序列，相当于我有 $4n-1$ 个 $0,1$ 序列然后对于每个 $i$ 询问有多少个不同的长度为 $i$ 的前缀（然后减掉 $i+1$，因为全 $0$ 和前 $i$ 个位置恰在某个位置放 $1$ 的序列都存在），那你先在叶子上建立动态开点线段树，没建立的位置填 $0$，然后在树上做线段树合并从而把儿子的序列异或起来得到父亲的，需要做一个持久化。然后得到每个结点的序列的线段树后，我们直接对每个长度的线段树结点做排序，可以将其视为两个儿子构成的二元组，用计数排序，就可以做到 $\mathcal{O}(n\log n)$ 排序了，然后排好序再通过线段树二分查询相邻两个的 LCP，依此建立出的笛卡尔树即为这些序列的压缩 Trie 树。

这样做的空间是 $\mathcal{O}(n\log n)$ 的，但是主播提出了一种线性空间的做法（相对难写但是跑得很快）：

考虑树上线段树合并的本质是让每个线段树区间只在它的端点构成的虚树上重新处理，于是我们做这样一件事：假如我们要处理出每个结点的序列的线段树上区间 $[l,r)$ 的信息：

• 如果 $r-l=1$：我们就直接拎出来那两个点以及它们的 LCA 处理下即可，我们约定不在虚树上的点如果有子树中点在虚树上就取那个结点的信息，否则设为全 $0$ 信息；
• 如果 $r-l>1$：我们将其劈成 $[l,m)$ 和 $[m,r)$，先递归下去处理这两个子树，再建立整个区间所有点的虚树，遵循前文提到的原则我们可以处理出虚树上每个结点的 $[l,m)$ 信息与 $[m,r)$ 信息，然后做计数排序，同时也可以维护出排序相邻的两项的 LCP，具体来说写一个 $\mathcal{O}(n)$ - $\mathcal{O}(1)$ 的 RMQ 即可，这样就不需要再访问线段树上子树内信息只需要记录这一层了。注意我们这里虽然需要会先存下左子树信息再进入右子树递归，但是你注意到你的递归栈上存的子树信息无交，因此这部分空间还是线性的。

轻松拿下最优解第一。