← 返回题目列表

Codeforces · 1899/G

G. 不寻常的娱乐

中文机器翻译题面 查看原题

树是没有循环的连通图。

排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 可以任意顺序。例如,$$$[5, 1, 3, 2, 4]$$$ 是一个排列,但 $$$[2, 1, 1]$$$ 不是一个排列(因为 $$$1$$$ 在数组中出现两次),并且 $$$[1, 3, 2, 5]$$$ 也不是一个排列(因为 $$$n = 4$$$,但 $$$5$$$ 出现在数组)。

BrMeast 视频拍摄失败后,Alex 陷入了抑郁。就连他的生日也没有让他高兴。不过,在收到蒂莫菲送来的礼物后,亚历克斯的心情突然好了起来。现在他花了好几天的时间和这位才华横溢的建造者一起玩。最近,他想出了一个不寻常的娱乐方式。

Alex 从他的构造函数中构建了一棵树,由 $$$n$$$ 个顶点组成,编号从 $$$1$$$ 到 $$$n$$$,根位于顶点 $$$1$$$。然后他按某种顺序写下从 $$$1$$$ 到 $$$n$$$ 的每个整数,获得排列 $$$p$$$。之后,Alex 提出了 $$$q$$$ 整数三元组 $$$l、r、x$$$。对于每个三元组,他尝试确定顶点 $$$p_l, p_{l+1}, \ldots, p_r$$$ 中是否至少存在一个顶点 $$$x$$$ 的后代。

顶点 $$$u$$$ 是顶点 $$$v$$$ 的后代当且仅当 $$$\mathrm{dist}(1, v) + \mathrm{dist}(v, u) = \mathrm{dist}(1, u)$$$,其中 $$$\mathrm{dist}(a, b)$$$ 是顶点之间的距离$$$a$$$ 和$$$b$$$。换句话说,顶点$$$v$$$必须位于从根到顶点$$$u$$$的路径上。

Alex 向 Zakhar 讲述了这项娱乐活动。现在亚历克斯告诉他的朋友 $$$q$$$ 如上所述的三倍,希望扎克哈可以检查是否有后代的存在。扎哈尔很困,所以他向你寻求帮助。帮助扎克哈回答亚历克斯的所有问题并最终入睡。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n, q$$$ ($$$1 \le n, q \le 10^5$$$) - 分别是树中的顶点数和问题数。

接下来的 $$$n - 1$$$ 行中的每一行都包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$),表示顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边(保证生成的图是一棵树)。

下一行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) — 排列 $$$p$$$ (保证从 $$$1$$$ 到 $$$n$$$ 的每个整数恰好出现一次)。

然后按照描述 Alex 问题的 $$$q$$$ 行进行操作。第 $$$i$$$ 行包含三个整数 $$$l, r, x$$$ ($$$1 \le l \le r \le n$$$, $$$1 \le x \le n$$$),如语句中所述。

保证所有测试用例的 $$$n$$$ 总和和 $$$q$$$ 总和不超过 $$$10^5$$$。

输出

对于 Alex 的每个问题,如果所描述的后代存在,则打印“Yes”(不带引号),否则打印“No”(不带引号)。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

3
3 5
1 2
2 3
1 2 3
1 2 2
1 2 3
2 3 1
1 2 3
2 3 3
10 10
2 6
2 7
2 4
1 7
2 8
10 6
8 5
9 4
3 4
10 2 5 9 1 7 6 4 3 8
8 9 8
7 8 1
7 10 6
4 8 9
5 5 10
7 10 1
9 9 2
9 10 6
6 6 2
10 10 6
1 1
1
1 1 1

输出 #1

YES
NO
YES
NO
YES

NO
YES
YES
YES
NO
YES
YES
NO
NO
NO

YES