The Parenthesis Tree
All submissions for this problem are available.
Samosa Bhai and Jalebi Bai are taking cooking classes from CodeChef. CodeChef, as the name suggests, is also a coding enthusiast. So he decides to get his pupils interested in coding.
For this, he takes them both to a strange tree made up of N nodes. Each of these nodes is of one of the following two types — nodes containing open parenthesis ‘(’ and nodes containing closed parenthesis ‘)’. CodeChef asks the students Q queries, where in each query they have to find out if the path between two given nodes is a balanced parentheses string or not. If they solve all the queries, they will get to eat the special Christmas cake made by CodeChef.
Samosa Bhai and Jalebi Bai are lazy kids, but they also want to eat the cake. So they ask you for help.
Note: A balanced parentheses string means that each opening parenthesis has a corresponding closing parenthesis and the pairs of parentheses are properly nested.
The first line contains T, the number of test cases to follow.
Each test case begins with N and Q, the number of nodes in the tree and the number of queries to follow.
N-1 lines follow. Each line contains 2 space-separated integers, x and y, which denotes that there is an edge between them.
The next line contains N space-separated parentheses. The ith parenthesis denotes the value on the ith node.
The Q queries follow. Each query contains two space-separated integers u and v.
For each query, output "Yes" [without quotes] if the path from u to v is a balanced parentheses string and "No" [without quotes] if the path from u to v is not a balanced parentheses string.
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 105
- 1 ≤ Q ≤ 3*105
- 1 ≤ Sum of N over all cases ≤ 105
- 1 ≤ Sum of Q over all cases ≤ 3*105
Input: 1 6 4 1 2 2 5 1 3 3 6 3 4 ) ( ) ) ( ( 5 3 3 5 2 4 6 2 Output: Yes No No No
Example case 1.
- Query 1: The path contains (()).
- Query 2: The path contains ))((.
- Query 3: The path contains ())).
- Query 4: The path contains ())(.
NOTE: Input files can be large. Please use fast input methods (E.g. scanf in C / C++, BufferedReader in Java)
|Tags||acm15kol, ancestors, balanced, common, devuy11, lowest, parentheses|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions
If you are still having problems, see a sample solution here.