‹ 上一题下一题 ›

j00513. DFS 序判祖先未做

1000 ms 256 MB 测试点 10 J-20·树上问题处理 J·数据结构自拟题树的概念树的表示与存储深度优先搜索

文件读写输入j00513.in输出j00513.out

题目描述

从根 DFS（孩子按编号升序），记录每个点的进出时间戳 $in / o u t$ 。 $u$ 是 $v$ 的**祖先（含自身）**当且仅当 $i n_{u} < i n_{v} \leq o u t_{u}$ 。 $q$ 次询问 $(u, v)$ 逐行输出 YES/NO。

输入格式

通用树 + 一行 $q$ + $q$ 行 $u v$ 。

输出格式

$q$ 行。

样例

输入

输出

YES
NO
YES

数据范围

$1 \leq n, q \leq 2 \times 1 0^{5}$
$1 \leq u < v \leq n$ （边端点）；询问中的 $u, v$ 满足 $1 \leq u, v \leq n$

输入

输出

答案