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.Input
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.
N1 lines follow. Each line contains 2 spaceseparated integers, x and y, which denotes that there is an edge between them.
The next line contains N spaceseparated parentheses. The ith parenthesis denotes the value on the ith node.
The Q queries follow. Each query contains two spaceseparated integers u and v.
Output
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.
Constraints
 1 ≤ T ≤ 1000
 1 ≤ N ≤ 10^{5}
 1 ≤ Q ≤ 3*10^{5}
 1 ≤ Sum of N over all cases ≤ 10^{5}
 1 ≤ Sum of Q over all cases ≤ 3*10^{5}
Example
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
Explanation
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)
Author:  devuy11 
Editorial  http://discuss.codechef.com/problems/KOL1503 
Tags  acm15kol, ancestors, balanced, common, devuy11, lowest, parentheses 
Date Added:  8122015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 