一、题目简化

有一个城市，有 (n) 个建筑物（编号 1 到 (n)），1 号是市中心。
建筑物之间有 (m) 条双向道路，整个城市的地图是一个“仙人掌”——意思是每条边最多在一个环上，并且从市中心可以到所有建筑物。

每个建筑物卖一种拉面，油腻程度是 (a_i)（正整数）。

特殊情景：
rin 在建筑物 (x) 时，假设从市中心 1 到 (x) 的所有简单路径上的道路都被堵死了，那么 rin 就被困在 (x) 所在的连通块里（无法离开这个块）。

在这个连通块里，rin 可以吃到这个块里所有建筑物的拉面（多次经过就多次吃）。

问题：
给定 (x) 和油腻值上限 (y)，以及 (ty)（0 或 1），问在这个连通块中：

• 油腻值 (\le y) 的拉面种类中：
  • 如果 (ty=0)：出现次数为 偶数 的种类数
  • 如果 (ty=1)：出现次数为 奇数 的种类数

二、关键转化

1. 连通块是啥？

在仙人掌图中，删掉 1 到 (x) 的所有简单路径的边后，(x) 所在的连通块，其实就是 DFS 树中 (x) 的某棵子树。

具体来说：

• 对图做 DFS（根为 1），得到每个点的进入时间 (in[u]) 和离开时间 (out[u])。
• 从 (x) 往上找，找到第一个点 (p)，它所在的环能通到 1 到 (x) 路径上的更早的点，那么连通块就是 (p) 的子树（去掉那些能直接回到更上面的部分）。
• 实际上可以证明：这个连通块在 DFS 序上是 一个连续区间 ([in[p], out[p]])。

所以问题变成：
给定一个区间（DFS 序区间），问区间内油腻值 (\le y) 的拉面种类，按出现次数奇偶性分类统计。

2. 问题变成区间数颜色（带奇偶）

我们有 (n) 个位置（DFS 序），每个位置有一个油腻值。
给一个区间 ([L,R]) 和 (y)，求：

• 油腻值 (\le y) 的颜色中，出现次数为偶数的颜色数（ty=0）
• 油腻值 (\le y) 的颜色中，出现次数为奇数的颜色数（ty=1）

三、算法选择

直接对每个询问扫区间太慢，因为 (n,Q) 可达 (10^5)。

1. 莫队算法

• 把询问按区间排序，用两个指针 (l,r) 在序列上移动，动态维护区间内每种油腻值的出现次数。
• 移动时，当某个油腻值的次数变化时，更新它的奇偶性。

2. 值域分块

油腻值 (a_i \le 10^6)，询问的 (y \le 10^6)。
我们维护：

• freq[v]：油腻值 (v) 在当前区间出现次数的奇偶（0 偶，1 奇）
• 把值域分成块，每块维护块内 出现次数为奇数的种类数。

插入/删除一个值 (v) 时：

• 如果原来出现次数是奇数，加入后变偶数，那么奇数种类数减 1
• 如果原来是偶数，加入后变奇数，那么奇数种类数加 1

查询时：

• 对值域块扫描，对油腻值 (\le y) 的块，累加奇数种类数，就能得到“油腻值 (\le y) 且出现次数为奇数的种类数”。
• 偶数的种类数 =（油腻值 (\le y) 的总种类数）−（奇数种类数）。总种类数可以类似用值域分块维护。

四、步骤总结

1. DFS 建树
   得到 DFS 序，把每个点对应的连通块映射成 DFS 序上的区间。

2. 莫队处理
   把询问按区间排序，用双指针维护区间，同时用值域分块维护奇偶信息。

3. 回答询问
   根据 (ty) 输出奇数或偶数种类数。

五、复杂度

• 莫队移动：(O(n\sqrt{Q}))
• 值域分块查询：(O(\sqrt{V})) 每次
• 总复杂度：(O(n\sqrt{Q} + Q\sqrt{V}))，可过 (10^5) 数据。