题目描述

给出五元组 $(T, I, S_V, S_E, \iota)$，其中：

• $T$ 是一棵 $n$ 个点的有根树 $T = (V, E)$，其中 $V$ 为 $T$ 的点集，$E$ 为 $T$ 的边集。树的节点被编号为 $1, 2, \ldots, n$，其中根节点编号为 $1$。
• $I$ 是一个集合，集合中的元素称作信息。其中有两个不同的特殊元素：单位元 $\epsilon$ 和不合法信息 $\bot$。
• 对于一般的信息，其都具有点集合和边集合两个属性。特别的，对于单位元，其只有边集合的属性，而对于不合法信息，其没有以上两种属性。

对于信息 $o \in I \setminus \{ \epsilon, \bot \}$，$o$ 的点集合是 $V$ 的一个二元子集，记作 $S_V(o)$，满足 $S_V(o) \subseteq V$ 且 $|S_V(o)| = 2$。其中，两个集合 $A, B$ 的差 $A \setminus B$ 被定义为 $A \setminus B = \{ x \in A \mid x \notin B \}$。

对于信息 $o \in I \setminus \{ \bot \}$，$o$ 的边集合是 $E$ 的一个子集，记作 $S_E(o)$，满足 $S_E(o) \subseteq E$。规定单位元的边集合为空，也即 $S_E(\epsilon) = \varnothing$。

对于树上的任何一条边 $e \in E$，记 $e = (u, v)$，存在一个关于 $e$ 的信息 $\iota(e) \in I$，它以其端点为点集合、自身为边集合，即 $S_V(\iota(e)) = \{ u, v \}$、$S_E(\iota(e)) = \{ e \}$。

信息有两种合并的方式，分别记作 $R$ 和 $C$。对于 $\forall a, b \in I$，记 $r = R(a, b), c = C(a, b)$，满足 $r, c \in I$，则：

• 单位元和任何信息合并都得到对方。也即，如果 $a = \epsilon$，那么 $r = c = b$；如果 $b = \epsilon$，那么 $r = c = a$。
• 不合法信息和任何信息合并都得到不合法信息。也即，如果 $a = \bot$ 或者 $b = \bot$，那么 $r = c = \bot$。
• 对于剩下的情况，如果两个信息的边集合的交集非空，或者点集合的交集的大小不为 $1$，则合并得到不合法信息。也即，如果 $S_E(a) \cap S_E(b) \ne \varnothing$ 或 $|S_V(a) \cap S_V(b)| \ne 1$，则 $r = c = \bot$。
• 否则，有 [ \begin{aligned} S_E(r) &= S_E(c) = S_E(a) \cup S_E(b), \ S_V(r) &= S_V(a), \ S_V(c) &= S_V(a) \oplus S_V(b), \end{aligned} ] 其中 $\oplus$ 表示集合的对称差运算，也即 $A \oplus B = (A \cup B) \setminus (A \cap B)$。

定义 $T$ 中两个点的树上距离为树上以两个点为端点的唯一简单路径经过的边数。

给出评分参数 $M$ 和 $q$ 次询问，每次询问给出树上的一个点 $u$ 和一个非负整数 $d$。记点集 $X$ 为 $T$ 中所有与 $u$ 的树上距离不超过 $d$ 的点构成的集合，又记边集 $Y = \{ (a, b) \in E \mid a, b \in X \}$ 为 $X$ 内部的边集。可以证明，从 $\epsilon$ 和所有 $\iota(e)$（$e \in E$）出发，总是能通过有限次 $R, C$ 的调用得到信息 $o \ne \bot$ 满足 $S_E(o) = Y$。

每组询问中，你需要在 $R$ 和 $C$ 的调用次数总和不超过 $M$ 的限制下构造出一个满足这样的要求的信息 $o$。特别地，如果 $d = 0$，则直接返回单位元 $\epsilon$ 即可。

---

实现细节

请确保你的程序开头有 #include "count.h"。

头文件 count.h 中实现了如下内容：

• 定义了信息对应的数据类型 info；
• 定义了 $\epsilon$ 所对应的 info 类型常量 emptyinfo，你可以在程序中直接使用。
• 定义并实现了以下两个信息合并函数，你可以在程序中直接调用：

  info MR(info a, info b);  // 返回 R(a, b)
  info MC(info a, info b);  // 返回 C(a, b)
  

  两个函数分别返回 $R(a, b)$ 与 $C(a, b)$ 对应的信息。
  你需要保证调用 $R(a, b)$ 与 $C(a, b)$ 时结果不为 $\bot$，否则程序可能会出现异常行为。
• 定义并实现了判定一个信息是否为单位元的函数，你可以在程序中直接调用：

  bool isempty(info a);  // 返回真当且仅当 a 为单位元
  

你不需要，也不应该实现主函数。你需要实现如下几个函数：

void init(int T, int n, int q, vector<int> fa, vector<info> e, int M);

• T 表示测试点编号，n 表示树的点数，q 表示询问数，M 表示该测试点的评分参数。
• fa 和 e 的长度均为 $n - 1$。对于 $0 \le i < n - 1$，fa[i] 和 $i + 2$ 为第 $i$ 条边 $e_i$ 的两个端点，e[i] 为题目描述中提到的 $\iota(e_i)$ 所对应的 info 类型元素。数据保证 fa[i] 小于 $i + 2$。

info ask(int u, int d);

给出一个询问，参数的意义见题目描述。你需要在函数结束时返回一个满足题设条件的信息。

---

样例

样例 1
见附件中的 count/count1.in 与 count/count1.ans。

样例 2
见附件中的 count/count2.in 与 count/count2.ans。
该组样例满足数据范围中的特殊性质 A。

样例 3
见附件中的 count/count3.in 与 count/count3.ans。
该组样例满足数据范围中的特殊性质 B。

样例 4
见附件中的 count/count4.in 与 count/count4.ans。

---

数据范围与提示

对于所有测试点，$1 \le n \le 2 \times 10^5$，$1 \le q \le 10^6$；每组询问中，有 $1 \le u \le n$，$1 \le d \le n - 1$。

特殊性质 A：保证 $\forall i \in [1, n - 1]$，编号为 $i + 1$ 的点的父节点为 $i$。
特殊性质 B：保证所有询问均满足 $u = 1$。
特殊性质 C：保证所有询问均满足 $d \le 100$。
特殊性质 D：保证所有询问均满足 $d \ge 1000$。