CF1843F2 Omsk Metro (hard version)

这是该问题的困难版本。与简单版本的唯一不同之处在于，本版本中 $u$ 可以取任意可能的值。 众所周知，Omsk 是 Berland 的首都。和所有首都一样，Omsk 拥有发达的地铁系统。Omsk 地铁由若干个车站组成，这些车站通过隧道连接，并且任意两个车站之间恰好有一条路径，每条隧道最多经过一次。换句话说，地铁系统是一棵树。 为了发展地铁并吸引居民，Omsk 采用了如下系统。每个车站都有自己的权值 $x \in \{-1, 1\}$。如果车站的权值为 $-1$，那么当 Omsk 居民经过该车站时，需要支付 $1$ burle 的费用。如果车站的权值为 $1$，则居民会获得 $1$ burle 的奖励。 目前 Omsk 地铁只有编号为 $1$ 且权值 $x=1$ 的一个车站。每天会发生以下两种事件之一： - 在编号为 $v_i$ 的车站上新建一个权值为 $x$ 的车站，并为其分配一个比现有车站数量大 $1$ 的编号。 - Omsk 的居民 Alex 想知道：在顶点 $u$ 和 $v$ 之间的路径上，是否存在一个子段（可以为空），使得经过该子段恰好可以赚取 $k$ burle（如果 $k

第一行包含一个整数 $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 \leq k_i \leq n$）。保证编号为 $u_i$ 和 $v_i$ 的顶点存在。此时需要判断，在编号为 $u_i$ 和 $v_i$ 之间的路径上，是否存在一个（可能为空的）子段，其上所有车站的权值之和恰好为 $k_i$。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每一个 Alex 的问题，如果存在满足条件的子段，输出 "Yes"（不带引号），否则输出 "No"（不带引号）。 输出时不区分大小写（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的答案）。

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