Description
You are given a rooted tree with $n$ nodes, numbered from $1$ to $n$.
The tree is specified by a parent array $p$, where $p_i$ denotes the parent of node $i$.
There is exactly one index $r$ such that $p_r = r$; this node $r$ is the root of the tree.
You will then receive $q$ queries.
Each query consists of three integers $a$, $b$, and $l$ and asks whether $a$ appears among the first $l$ strict ancestors of $b$ in the tree rooted at $r$.
Definition:
For a node $b$ and an integer $l \ge 1$, consider the unique path from $b$ upward toward the root $r$, excluding $b$ itself.
Let $\mathrm{UP}_l(b)$ be the set consisting of the first $l$ distinct nodes on this path (if fewer than $l$ strict ancestors exist, then $\mathrm{UP}_l(b)$ contains all strict ancestors of $b$).
A query $(a,b,l)$ is answered Yes if and only if $a \in \mathrm{UP}_l(b)$; otherwise, No.
Constraints
- $1 \le n \le 3 \times 10^5$
- $1 \le q \le 3 \times 10^5$
- $1 \le p_i \le n$
- Exactly one index $r$ such that $p_r = r$
- $1 \le a_i,b_i \le n$
- $1 \le l_i \le n$
- $\forall i,a_i \neq b_i$
Subtasks
- Testcases 1, 2 : $q \le 10$
- Testcases 3, 4 : $l_i = n$
- Testcases 5, 6 : No further constraints.
Input
$n$ $q$
$p_1$ $p_2$ ... $p_n$
$a_1$ $b_1$ $l_1$
$a_2$ $b_2$ $l_2$
...
$a_q$ $b_q$ $l_q$ |
The input consists of the following:
The first line contains two integers $n$ and $q$, the number of nodes and the number of queries.
The second line contains $n$ integers $p_1, p_2, \ldots, p_n$, representing the parent array.
Each of the next $q$ lines contains three integers $a_j, b_j, l_j$, representing a query asking whether $a_j \in \mathrm{UP}_{l_j}(b_j)$.
Output
For each query, output a single line:
- Output
Yes if $a$ is among the first $l$ strict ancestors of $b$.
- Output
No otherwise.
The output for each query should be followed by a newline (including the last one).
Tags