← 返回题目列表

Codeforces · 1843/F2

F2. 鄂木斯克地铁(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。简单版本和困难版本之间的唯一区别是,在此版本中 $$$u$$$ 可以采用任何可能的值。

众所周知,鄂木斯克是贝尔兰的首都。与任何首都一样,鄂木斯克拥有发达的地铁系统。鄂木斯克地铁由一定数量的车站组成,车站之间通过隧道相连,任意两个车站之间只有一条路径,每条隧道经过的次数不超过一次。换句话说,地铁是一棵树。

为了发展地铁并吸引居民,鄂木斯克使用了以下系统。每个站点都有自己的权重 $$$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$$$Subsegment — 连续的元素序列。

输入

第一行包含一个数字 $$$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$$$的子段(可能为空)。

保证所有测试用例的 $$$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
7
+ 1 -1
+ 2 -1
+ 2 1
+ 3 -1
? 5 2 2
? 3 1 -1
? 5 4 -3

输出 #2

NO
YES
YES

注意

第一个示例的说明。

第二个问题的答案是“是”,因为有一条路径$$$1$$$。

第四题,我们可以再次选择$$$1$$$路径。

在第五个查询中,答案是“是”,因为存在路径$$$1-3$$$。

在第六个查询中,我们可以选择一个空路径,因为它的权重总和是 $$$0$$$。

不难证明没有满足第一和第三个查询的路径。