1. 核心算法概览

本题包含两个子问题：

1. 查询 1 (1 x y)：求 $x$ 到 $y$ 路径上的本质不同颜色数。这是经典的 树上莫队 问题。
2. 查询 2 (2 A B)：求从 $1 \to A$ 路径上任选点 $x$，从 $1 \to B$ 路径上任选点 $y$，路径 $x \to y$ 颜色数的期望。
   • 期望 $\times$ 总方案数 $=$ 所有组合的颜色数之和。
   • 这是一个高维统计问题，可以通过 差分 和 贡献法 转化为区间历史和问题，结合莫队算法维护。

2. 解题思路详解

子问题 1：路径颜色数（树上莫队）

对于树上路径查询，通常使用欧拉序（Euler Tour）或者 DFS 序将树上路径转化为线性区间。 这份代码采用的是 DFS 序 + 差分 的方式（虽然莫队通常处理欧拉序，但这里结合了 vis 数组进行节点的显隐操作，即 XOR 莫队 的思想）。

• 区间转化：
  • 对于路径 $u \to v$（设 $dfn[u] < dfn[v]$），如果是直链（$u$ 是 $v$ 的祖先），对应区间 $[dfn[u], dfn[v]]$。
  • 如果不是直链，对应区间 $[dfn[u], dfn[v]]$，但需要额外处理 $LCA(u, v)$。
• 状态维护：
  • 使用 cnt[color] 记录当前区间内颜色的出现次数。
  • 使用 vis[node] 记录节点是否在当前区间内（处理路径时，出现两次的节点会抵消，代表不在路径上）。
  • 变量 res 维护当前的本质不同颜色数量。

子问题 2：期望/总和查询（贡献法 + 链表维护）

这是本题的难点。要求 $\sum_{x \in Path(1, A)} \sum_{y \in Path(1, B)} \text{CountDistinct}(Path(x, y))$。

直接做非常困难，代码中利用了差分思想：

• 预处理 $f[u]$：表示 $1 \to u$ 这条链上所有点对的颜色数贡献（代码中 dfsp 函数）。
• 利用 LCA 性质，将 $A$ 和 $B$ 的询问拆解为若干个关键点区间的询问。
  • 代码中 ans[i] = f[u] + f[v] - dep[lc] 是基础差分。
  • 后续加入的 qr[++m] 是为了处理交叉部分的贡献，将树上的矩形区域查询转化为了莫队能够处理的线性区间查询。

贡献法的计算公式： 对于一个颜色 $C$，它在当前区间（对应树上一条路径或点集）内的贡献等于：

为了在 $O(1)$ 时间内维护“不包含颜色 $C$ 的子路径数”，代码在莫队移动指针时维护了一个 双向链表：

• 链表结构：pr[x], nx[x] 记录当前区间内，节点 $x$ 在某种顺序下的前驱和后继（同色节点）。
• 距离计算：st.dis(p, r) 计算树上距离。
• 变量含义：
  • ds: 当前区间内的节点总数。
  • sd: 当前所有颜色内部相邻节点距离产生的“无效子路径”贡献和。
  • sl1, sl2: 维护左端点相关的距离一次项和二次项（用于快速计算加入左端点时的贡献）。
  • sr1, sr2: 维护右端点相关的距离一次项和二次项。

代码中的 query(2) 函数就是利用这些变量，通过公式算出当前的贡献总和：

ll ans = 1ll * ds * (ds + 1) / 2 * res - sd; // 总可能 - 内部间隔造成的无效
ans -= (sl2 + sl1) / 2; // 减去左边界造成的无效
ans -= (sr2 + sr1) / 2; // 减去右边界造成的无效

3. 代码结构分析

1. 输入与预处理：

   • IO 优化：namespace IO 处理了快读快写，因为数据量较大（$M=2 \times 10^5$）。
   • 随机生成：题目为了减小输入文件大小，使用了 LCG 生成器生成树边和颜色。
   • ST 表 (ST_table)：用于 $O(1)$ 查询 LCA 和 $O(1)$ 查询树上两点距离 dis(u, v)。同时实现了 find(x, y) 寻找 $x$ 在 $y$ 方向上的儿子（Level Ancestor）。

2. 莫队核心 (insL, insR, delL, delR)：

   • 这四个函数非常关键，它们不仅维护 cnt 和 res（用于查询 1），还维护了链表和 sd, sl, sr 等变量（用于查询 2）。
   • 例如 insL(p)：在左侧插入节点 $p$。
     • 如果 $p$ 的颜色是第一次出现，更新 fir（首位）、las（末位），并更新边界贡献 sr2, sr1 等。
     • 如果不是第一次，找到当前该颜色的首位 fir，建立链接，计算 $p$ 和 fir 之间的距离 d，从 sl（左边界贡献）中扣除这部分，并加入到 sd（内部贡献）中。

3. 主处理流程：

   • 先 DFS 建立 ST 表。
   • dfsp 预处理 $f[x]$。
   • 处理询问：
     • 类型 1：直接加入莫队查询队列。
     • 类型 2：拆分为差分项和莫队查询项。这里使用了复杂的差分拆解，将 $Query(u, v)$ 拆成了 $u, v, LCA(u,v)$ 及其儿子相关的多个查询。
   • 莫队排序：使用奇偶性优化（Hilbert 曲线或者块内奇偶排序）来最小化指针移动距离。B = tim / sqrt(m + 1) + 1 计算块大小。
   • 莫队执行：
     • curL, curR 移动时调用 updL, updR。
     • upd 函数中利用 vis 数组做 XOR 操作（存在则删，不存在则加），这是处理树上路径莫队的标准技巧。

4. 复杂度

• 时间复杂度：$O((N+M)\sqrt{N})$。莫队算法的标准复杂度。由于操作较多（链表维护、距离计算），常数较大，但 ST 表求距离是 $O(1)$ 的，保证了效率。
• 空间复杂度：$O(N + M)$。

5. 总结

这道题是数据结构综合应用的典范：

1. 问题转化：利用差分将高维期望问题转化为区间和问题。
2. 算法选择：树上莫队处理离线区间查询。
3. 数据结构：动态维护链表和统计变量来支持 $O(1)$ 的贡献计算。

代码中使用 basic_string 代替 vector 以优化内存和速度，手写 IO，以及 ST 表求 LCA，都是为了在 10s 的时限内通过 $10^5$ 级别的数据（考虑到莫队的根号复杂度和大常数）。