Codeforces Round 881 (Div. 3) |
---|
Finished |
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:
You are a friend of Alex, so your task is to answer Alex's questions.
$$$\dagger$$$Subsegment — continuous sequence of elements.
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:
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$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).
18+ 1 -1? 1 1 2? 1 2 1+ 1 1? 1 3 -1? 1 1 1? 1 3 2? 1 1 0
NO YES NO YES YES YES
110+ 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
YES NO YES YES NO
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.
Name |
---|