动态地铁路径

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

题目描述

地铁网络是一棵带点权树，每个点权为 $-1$ 或 $1$。初始时只有编号为 $1$、权值为 $1$ 的顶点。

依次处理两类事件：

• + v x：新建一个权值为 $x$ 的顶点，把它与已有顶点 $v$ 相连。新顶点编号为当前顶点总数加一。
• ? u v k：询问顶点 $u$ 到 $v$ 的简单路径上，是否存在一个连续子段，使子段点权和恰为 $k$。子段可以为空，空子段的和为 $0$。

输入格式

第一行一个整数 $t$，表示测试组数。

每组第一行一个整数 $n$，表示事件数。接下来 $n$ 行，每行是上述一种事件。

输出格式

对每个询问输出一行 YES 或 NO。

样例输入 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\le t\le10^4$；
• 每组 $1\le n\le2\times10^5$，所有测试组的 $n$ 之和不超过 $2\times10^5$；
• 新建事件中，父节点已存在且 $x\in\{-1,1\}$；
• 询问事件中，两个端点均已存在且 $-n\le k\le n$。

所有测试点相互独立计分。