题意理解

我们有两棵树：

• 小A树：$n \leq 20$ 个节点
• 小B树：$m \leq 2 \times 10^5$ 个节点

每个节点有一个颜色，支持两种操作：

1. 查询：给定 $P_1, P_2, D_1, D_2$，求小A树中 $P_1$ 子树内距离不超过 $D_1$ 的节点与小B树中 $P_2$ 子树内距离不超过 $D_2$ 的节点的颜色并集大小
2. 修改：修改小A树某个节点的颜色

关键特性：查询是强制在线的，$D_1, D_2$ 需要与上次答案异或。

核心思路

关键观察 1：利用小A树的大小

由于 $n \leq 20$，我们可以：

• 预处理小A树的所有可能查询
• 对小A树进行状态压缩或暴力枚举
• 为每个节点预处理其子树内距离不超过各种值的颜色集合

关键观察 2：问题分解

将查询分解为：

$$|C_A \cup C_B| = |C_A| + |C_B| - |C_A \cap C_B|$$

其中：

• $C_A$：小A树中满足条件的颜色集合
• $C_B$：小B树中满足条件的颜色集合

关键观察 3：处理大B树

对于大B树 ($m \leq 2 \times 10^5$)，需要高效数据结构：

• 使用 DFS 序 将子树查询转化为区间查询
• 使用 树上倍增 处理距离限制
• 使用 线段树 或 分块 维护颜色信息

算法框架

预处理阶段

小A树预处理 ($n \leq 20$)：

1. 为每个节点 $u$ 预处理：
   • 子树节点集合
   • 到子树内各节点的距离
   • 对每个可能的距离 $d$，预处理该距离内的颜色集合

大B树预处理：

1. 计算 DFS 序 和欧拉序
2. 预处理 LCA 和树上倍增数组
3. 建立线段树维护颜色信息

查询处理

对于查询 $(P_1, P_2, D_1, D_2)$：

步骤 1：处理小A树

• 由于 $n$ 很小，直接枚举 $P_1$ 子树内距离 $\leq D_1$ 的所有节点
• 得到颜色集合 $C_A$

步骤 2：处理大B树

• 在 DFS 序上，$P_2$ 子树对应一个区间 $[l, r]$
• 距离限制转化为：节点深度 $depth[x] \leq depth[P_2] + D_2$
• 使用线段树查询区间 $[l, r]$ 内满足深度限制的颜色集合 $C_B$

步骤 3：合并答案

• 计算 $|C_A \cup C_B| = |C_A| + |C_B| - |C_A \cap C_B|$
• 其中 $|C_A \cap C_B|$ 需要对每个 $c \in C_A$ 检查是否在 $C_B$ 中出现

修改处理

对于修改操作 $(S_1, S_2)$：

• 只影响小A树，直接更新预处理的信息
• 由于 $n$ 很小，重新计算影响的集合代价可接受

复杂度分析

预处理复杂度

• 小A树：$O(n^3)$
  • 需要为每个节点预处理子树信息和距离信息
  • 由于 $n \leq 20$，实际计算量可接受
• 大B树：$O(m \log m)$
  • DFS序和欧拉序：$O(m)$
  • LCA和树上倍增：$O(m \log m)$
  • 线段树构建：$O(m)$

查询复杂度

• 单次查询：$O(n + \log m)$
  • 小A树处理：$O(n)$，枚举子树内满足距离限制的节点
  • 大B树处理：$O(\log m)$，线段树区间查询
  • 集合合并：$O(n)$，计算颜色并集
• 总查询：$O(q \cdot (n + \log m))$
  • 其中 $q \leq 10^6$，$n \leq 20$，$m \leq 2 \times 10^5$

修改复杂度

• 单次修改：$O(n)$
  • 只影响小A树，更新相关预处理信息
• 总修改：$O(k \cdot n)$，其中 $k$ 是修改操作次数

空间复杂度

• 小A树：$O(n^2)$ 存储距离和子树信息
• 大B树：$O(m \log m)$ 存储倍增数组和线段树
• 颜色信息：$O(n + m)$ 存储节点颜色

总结

本题的核心在于利用数据范围的不平衡性：

• 小A树：$n \leq 20$ 允许暴力或状态压缩
• 大B树：$m \leq 2 \times 10^5$ 需要高效数据结构

关键技术：

1. 问题分解：将两棵树的问题分离处理
2. 数据结构选择：根据数据规模选择合适算法
3. 强制在线处理：设计实时查询算法
4. 位运算优化：高效处理集合运算

这是一个典型的需要根据数据特征设计算法的难题，考察选手对数据结构组合和算法优化的深刻理解。