CF1843F1 Omsk Metro (simple version)

这是该问题的简单版本。简单版与困难版的唯一区别在于本题中 $u = 1$。 众所周知，Omsk 是 Berland 的首都。与所有首都一样，Omsk 拥有发达的地铁系统。Omsk 地铁由若干个车站组成，这些车站通过隧道连接，并且任意两站之间恰好有一条路径，每条隧道最多经过一次。换句话说，地铁系统是一棵树。 为了发展地铁并吸引居民，Omsk 采用了如下制度。每个车站都有自己的权值 $x \in \{-1, 1\}$。如果车站的权值为 $-1$，那么当 Omsk 居民经过该站时，需要支付 $1$ burle 的费用。如果车站的权值为 $1$，则居民会获得 $1$ burle 的奖励。 目前，Omsk 地铁只有一个编号为 $1$ 且权值为 $x = 1$ 的车站。每天会发生以下两种事件之一： - 向编号为 $v_i$ 的车站添加一个新的车站，权值为 $x$，新车站的编号为当前车站总数加一。 - Alex（Omsk 的居民）想知道：在顶点 $u$ 和 $v$ 之间的路径上，是否存在一个子段（可以为空），使得经过该子段恰好可以获得 $k$ burle（如果 $k < 0$，则表示需要花费 $k$ burle）。换句话说，Alex 想知道在该路径上是否存在一个子段，其所有顶点权值之和恰好等于 $k$。注意，子段可以为空，此时权值和为 $0$。 你是 Alex 的朋友，你的任务是回答 Alex 的所有问题。 $^\dagger$ 子段——连续的一段元素。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示事件的数量。 接下来有 $n$ 行，每行描述一个事件。第 $i$ 行有以下两种可能： - 首先是符号“+”，然后是两个整数 $v_i$ 和 $x_i$（$x_i \in \{-1, 1\}$，保证编号为 $v_i$ 的顶点存在）。此时，向编号为 $v_i$ 的车站添加一个权值为 $x_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 \times 10^5$。

对于每一个 Alex 的问题，如果存在满足条件的子段，输出 “Yes”，否则输出 “No”。 你可以用任意大小写输出答案（如 "yEs"、"yes"、"Yes"、"YES" 都会被认为是正确的正答）。

第一个样例的解释： 第二个问题的答案是 “Yes”，因为存在路径 $1$。 第四个问题，我们同样可以选择路径 $1$。 第五个询问，答案是 “Yes”，因为存在路径 $1-3$。 第六个询问，我们可以选择空路径，因为其权值和为 $0$。 不难证明，对于第一个和第三个询问，没有满足条件的路径。 由 ChatGPT 4.1 翻译