Problem G: Ancestor
Problem G: AncestorTime Limit: 1 Sec Memory Limit: 128 MB
Submit: 1478 Solved: 185
Ella has a tree of n nodes. There are m queries, and each query has two integers x and y to ask whether y is an ancestor of x or not, and x is an ancestor of x. However, Ella does not know how to deal with it. Please find a solution.
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be two integers n(1 <= n <= 1.5*105) and m(1 <= m <= 1.5*105). The following are n - 1 lines, and each line will be two integers x and y, which means that y is the father of x. The following are m lines, and each line will be two integers x and y, which means a query(x, y). If y is an ancestor of x, output Yes, else output No.
For each test output m lines to answer the queries.