这是问题的简单版本。简单版本和困难版本之间的唯一区别是,在此版本中 $$$u = 1$$$。
众所周知,鄂木斯克是贝尔兰的首都。与任何首都一样,鄂木斯克拥有发达的地铁系统。鄂木斯克地铁由一定数量的车站组成,车站之间通过隧道相连,任意两个车站之间只有一条路径,每条隧道经过的次数不超过一次。换句话说,地铁是一棵树。
为了发展地铁并吸引居民,鄂木斯克使用了以下系统。每个站点都有自己的权重 $$$x \in \{-1, 1\}$$$。如果车站的重量为$$$-1$$$,那么当鄂木斯克居民访问车站时,将收取$$$1$$$ burle的费用。如果车站的重量为$$$1$$$,则鄂木斯克居民将获得$$$1$$$ burle 奖励。
鄂木斯克地铁目前只有一个车站,编号为$$$1$$$,重量为$$$x = 1$$$。每天都会发生以下事件之一:
- 权重为 $$$x$$$ 的新站点被添加到编号为 $$$v_i$$$ 的站点中,并且为其分配的编号比现有站点的数量大 1。
- 住在鄂木斯克的 Alex 想知道:顶点 $$$u$$$ 和 $$$v$$$ 之间的路径是否存在子段 $$$\dagger$$$ (可能为空),这样,通过沿着它旅行,可以准确地获得 $$$k$$$ burles(如果 $$$k < 0$$$,这意味着 $$$k$$$ burles必须花在旅行上)。换句话说,Alex 感兴趣的是路径中是否存在这样的子段,其中的顶点权重之和等于 $$$k$$$。注意,子段可以为空,那么总和等于$$$0$$$。
你是Alex的朋友,所以你的任务是回答Alex的问题。
$$$\dagger$$$子段 — 连续的元素序列。
输入
第一行包含一个数字 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含数字 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 事件数。
然后有 $$$n$$$ 行描述事件。在第 $$$i$$$ 行中,可以使用以下选项之一:
- 首先是符号“+”(不带引号),然后是两个数字$$$v_i$$$和$$$x_i$$$($$$x_i \in \{-1, 1\}$$$,也保证编号为$$$v_i$$$的顶点存在)。在这种情况下,权重为 $$$x_i$$$ 的新站点将添加到编号为 $$$v_i$$$ 的站点中。
- 首先出现符号“?” (不带引号),然后是三个数字 $$$u_i$$$、$$$v_i$$$ 和 $$$k_i$$$ ($$$-n \le k_i \le n$$$)。保证编号为 $$$u_i$$$ 和 $$$v_i$$$ 的顶点存在。在这种情况下,需要确定站$$$u_i$$$和$$$v_i$$$之间的路径是否存在权重总和恰好等于$$$k_i$$$的子段(可能为空)。在此版本的任务中,保证 $$$u_i = 1$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于 Alex 的每个问题,如果条件中描述的子段存在,则输出“Yes”(不带引号),否则输出“No”(不带引号)。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
示例
输入 #1
1 8 + 1 -1 ? 1 1 2 ? 1 2 1 + 1 1 ? 1 3 -1 ? 1 1 1 ? 1 3 2 ? 1 1 0
输出 #1
NO YES NO YES YES YES
输入 #2
1 10 + 1 -1 + 1 -1 + 3 1 + 3 -1 + 3 1 ? 1 6 -1 ? 1 6 2 ? 1 2 0 ? 1 5 -2 ? 1 4 3
输出 #2
YES NO YES YES NO
注意
第一个示例的说明。
第二个问题的答案是“是”,因为有一条路径$$$1$$$。
第四题,我们可以再次选择$$$1$$$路径。
在第五个查询中,答案是“是”,因为存在路径$$$1-3$$$。
在第六个查询中,我们可以选择一个空路径,因为它的权重总和是 $$$0$$$。
不难证明没有满足第一和第三个查询的路径。