Omsk Metro (simple version)

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

这是本题的简单版本。简单版与困难版的唯一区别是：本题的每次询问均保证 $u=1$。

Omsk 地铁由若干车站和隧道组成，任意两个车站之间恰好有一条简单路径，因此地铁结构是一棵树。每个车站有权值 $x\in\{-1,1\}$：经过权值为 $-1$ 的车站会花费 $1$ burle，经过权值为 $1$ 的车站会获得 $1$ burle。

最初只有编号为 $1$、权值为 $1$ 的车站。随后依次发生 $n$ 个事件：

• + v x：新建一个权值为 $x$ 的车站，并用隧道把它与已有车站 $v$ 相连。新车站编号为当前车站总数加一。
• ? u v k：询问从 $u$ 到 $v$ 的简单路径上，是否存在一段连续的车站（允许为空），使这些车站的权值和恰好为 $k$。本题保证 $u=1$。空段的权值和为 $0$。

请回答所有询问。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

每个测试用例的第一行包含一个整数 $n$，表示事件数。

接下来 $n$ 行，每行是以下两种格式之一：

• + v x，其中 $v$ 是已存在的车站编号，$x\in\{-1,1\}$；
• ? u v k，其中 $u,v$ 均为已存在的车站编号，且本题保证 $u=1$。

输出格式

对于每个询问，若存在满足条件的连续段，输出 Yes；否则输出 No。

答案不区分大小写，例如 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\le t\le 10^4$；
• $1\le n\le 2\times 10^5$；
• 所有测试用例的 $n$ 之和不超过 $2\times 10^5$；
• $-n\le k\le n$；
• 每次操作引用的车站均已存在，且每次询问满足 $u=1$。