Omsk Metro (simple version)
Contest: Codeforces Round 881 (Div. 3)
Difficulty rating: 1800
Tags: data structures, dfs and similar, dp, graphs, greedy, math, trees

This is the simple version of the problem. The only difference between the simple and hard versions is that in this version $$$u = 1$$$.

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 < 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.

Input format:
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$$$. In this version of the task, it is guaranteed that $$$u_i = 1$$$.

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

Output format:
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).

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
1
8
+ 1 -1
? 1 1 2
? 1 2 1
+ 1 1
? 1 3 -1
? 1 1 1
? 1 3 2
? 1 1 0

Example output:
NO
YES
NO
YES
YES
YES

Example input:
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

Example output:
YES
NO
YES
YES
NO

Editorial:
Let $$$\mathrm{mx}$$$ be the maximal sum on the path subsegment, $$$\mathrm{mn}$$$ — the minimal sum on the path subsegment. Then it is said that a subsegment with sum $$$x$$$ exists if and only if $$$\mathrm{mn} \leq x \leq \mathrm{mx}$$$.
Proof: Let us fix the subsegment with the minimum sum and the subsegment with the maximum sum. Now, we want to go from the first segment to the second one by consecutively removing or adding elements from the ends of the segment. Note that, due to the fact that $$$x \in \{-1, 1\}$$$, for each such action, the sum on the segment will change by exactly $$$1$$$. In other words, no matter how we go from one segment to another, the sum will remain a discretely continuous value. Then, since this function takes values of the minimum and maximum sum, it also takes all values from the segment between them (by the intermediate value theorem). Thus, the set of all possible sums on the subsegments is the interval of integers between the minimum and maximum sum, from which the original assumption follows.
Now, we have turned the problem down to finding the subsegment with the minimum and maximum sum on the path in the tree. Let $$$\mathrm{mx}_u$$$ be the maximum sum on the subsegment on the path from $$$1$$$ to $$$u$$$, $$$\mathrm{suf}_u$$$ — the maximum sum on the suffix of the path from $$$1$$$ to $$$u$$$, $$$p_u$$$ — the ancestor of vertex $$$u$$$, $$$x_u$$$ — its weight. Then $$$\mathrm{suf}_u = \max({0, \mathrm{suf}_{p_u} + x_u})$$$, $$$\mathrm{mx}_u = \max({\mathrm{mx}_{p_u}, \mathrm{suf}_u})$$$. Thus, we have learned to calculate the necessary values for a vertex immediately at the moment of its addition, which allows us to solve the problem online (but it is not required in the problem itself). The values for the minimum are counted in the same way.
Total complexity: $$$O(n)$$$.