CF1843F2.Omsk Metro (hard version)

This is the hard version of the problem. The only difference between the simple and hard versions is that in this version $u$ can take any possible value.

As is known, Omsk is the capital of Berland. Like any capital, Omsk has a well-developed metro system. The Omsk metro consists of a certain number of stations connected by tunnels, and between any two stations there is exactly one path that passes through each of the tunnels no more than once. In other words, the metro is a tree.

To develop the metro and attract residents, the following system is used in Omsk. Each station has its own weight $x \in {-1, 1}$. If the station has a weight of $-1$, then when the station is visited by an Omsk resident, a fee of $1$ burle is charged. If the weight of the station is $1$, then the Omsk resident is rewarded with $1$ burle.

Omsk Metro currently has only one station with number $1$ and weight $x = 1$. Every day, one of the following events occurs:

• A new station with weight $x$ is added to the station with number $v_i$, and it is assigned a number that is one greater than the number of existing stations.
• Alex, who lives in Omsk, wonders: is there a subsegment$\dagger$ (possibly empty) of the path between vertices $u$ and $v$ such that, by traveling along it, exactly $k$ burles can be earned (if $k \lt 0$, this means that $k$ burles will have to be spent on travel). In other words, Alex is interested in whether there is such a subsegment of the path that the sum of the weights of the vertices in it is equal to $k$. Note that the subsegment can be empty, and then the sum is equal to $0$.

You are a friend of Alex, so your task is to answer Alex's questions.

$\dagger$Subsegment — continuous sequence of elements.

这是该问题的困难版本。简单版本与困难版本的唯一区别在于：在本版本中，$u$ 可取任意可能的值。

众所周知，鄂木斯克（Omsk）是贝尔兰（Berland）的首都。如同任何首都一样，鄂木斯克拥有发达的地铁系统。鄂木斯克地铁由若干车站通过隧道连接而成，且任意两个车站之间恰好存在一条路径，该路径至多经过每条隧道一次。换言之，该地铁系统构成一棵树。

为发展地铁并吸引市民，鄂木斯克采用如下机制：每个车站具有一个权值 $x \in \{-1, 1\}$。若某车站权值为 $-1$，则当鄂木斯克市民访问该站时，需缴纳 $1$ 卢布（burle）费用；若权值为 $1$，则该市民将获得 $1$ 卢布奖励。

目前，鄂木斯克地铁仅有一个编号为 $1$ 的车站，其权值 $x = 1$。每天发生以下事件之一：

• 向编号为 $v_i$ 的车站添加一个权值为 $x$ 的新车站，该新车站的编号为当前已有车站总数加 $1$；
• 居住在鄂木斯克的 Alex 提出疑问：在顶点 $u$ 与 $v$ 之间的路径上，是否存在一个子段$\dagger$（可以为空），使得沿该子段行走恰好可赚取 $k$ 卢布（若 $k < 0$，则表示需花费 $|k|$ 卢布）。换言之，Alex 想知道：该路径上是否存在某个子段，使其所包含顶点的权值之和恰好等于 $k$。注意：子段可以为空，此时其权值之和为 $0$。

作为 Alex 的朋友，你的任务就是回答 Alex 的这些询问。

$\dagger$子段——元素的连续序列。

The first line contains a single number $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains the number $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of events.

Then there are $n$ lines describing the events. In the $i$-th line, one of the following options is possible:

• First comes the symbol "+" (without quotes), then two numbers $v_i$ and $x_i$ ($x_i \in {-1, 1}$, it is also guaranteed that the vertex with number $v_i$ exists). In this case, a new station with weight $x_i$ is added to the station with number $v_i$.
• First comes the symbol "?" (without quotes), and then three numbers $u_i$, $v_i$, and $k_i$ ($-n \le k_i \le n$). It is guaranteed that the vertices with numbers $u_i$ and $v_i$ exist. In this case, it is necessary to determine whether there is a subsegment (possibly empty) of the path between stations $u_i$ and $v_i$ with a sum of weights exactly equal to $k_i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$ 的站点存在）。此时，向编号为 $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$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each of Alex's questions, output "Yes" (without quotes) if the subsegment described in the condition exists, otherwise output "No" (without quotes).

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

对于 Alex 的每个问题，如果满足条件的子段存在，则输出 “Yes”（不带引号），否则输出 “No”（不带引号）。

您可以以任意大小写形式输出答案（例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被识别为肯定回答）。

Explanation of the first sample.

The answer to the second question is "Yes", because there is a path $1$.

In the fourth question, we can choose the $1$ path again.

In the fifth query, the answer is "Yes", since there is a path $1-3$.

In the sixth query, we can choose an empty path because the sum of the weights on it is $0$.

It is not difficult to show that there are no paths satisfying the first and third queries.

第一个样例的解释。

第二个问题的答案是“是”，因为存在路径 $1$。

在第四个问题中，我们可以再次选择路径 $1$。

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

在第六个查询中，我们可以选择空路径，因为其上边权之和为 $0$。

不难证明，不存在满足第一个和第三个查询的路径。