一、题目简化

有一个城市，有 $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$。
我们维护：

• $\text{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$ 数据。