Ancestor - MarisaOJ: Marisa Online Judge

Given a tree with

$n$ vertices rooted at

$1$ . There are

$q$ queries, each consisting of two vertices

$u$ and

$v$ . Determine whether

$u$ is an ancestor of

$v$ ,

$v$ is an ancestor of

$u$ , or neither. Define ancestor: Let

$p_i$ be the immediate parent of

$i$ in the tree. We have

$p_u$ as the ancestor of

$u$ ,

$p_{p_u}$ as the ancestor of

$u$ ,

$p_{p_{p_u}}$ as the ancestor of

$u$ , and so on. In other words, the parent of

$u$ is the ancestor of

$u$ , the parent of the parent of

$u$ is the ancestor of

$u$ , and so on. ### Input - The first line contains two integers

$n$ and

$q$ . - The next

$n-1$ lines each contain two integers

$u$ and

$v$ , indicating there is an edge between

$u$ and

$v$ . - The next

$q$ lines each contain two integers

$u$ and

$v$ , representing a query. Ensure

$u \neq v$ . ### Output - For each query, print: +

$MA$ if

$u$ is an ancestor of

$v$ . +

$RI$ if

$v$ is an ancestor of

$u$ . +

$SA$ otherwise. ### Constraints -

$1 \le n,q \le 10^5$ . -

$1 \le u, v \le n$ . ### Example Input:

$6 6 3 4 4 5 5 6 3 2 5 1 5 6 4 3 6 2 5 1 3 5 6 4$

Output:

$MA MA SA RI RI SA$

Euler tour
	Subtree queries
	Subtree update
	Ancestor
	Shallow
	Remove subtree
	Queries on tree
	Queries on tree 2
	Library
	Black vertices

Topic

Tree

Rating

1400

Solution (0)

Solution