Skip to content

1415: dfs 序的应用

题目

题目描述

给一棵 $n$ 个点的以 $1$ 为根的树,$Q$ 次询问两个点 $x, y$,回答 $y$ 是否为 $x$ 的祖先。

PS:在本题中,不认为自己是自己的祖先。

输入格式

第一行两个整数 $n, Q$ 表示树的大小和询问次数。

接下来 $n - 1$ 行,每行两个数 $x, y$ 表示 $x$ 和 $y$ 之间有一条边。

接下来 $Q$ 行每行两个数 $x, y$,询问 $y$ 是否为 $x$ 的祖先。

输出格式

$Q$ 行答案,若 $y$ 为 $x$ 的祖先则输出 Yes,否则输出 No

样例输入

5 5 1 2 3 1 4 2 5 2 1 2 3 1 4 1 1 4 3 1

样例输出

No Yes Yes No Yes

数据范围

$1\leq n, Q \leq 10^5$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!