CF1899G Unusual Entertainment

一棵树是一个无环连通图。 排列是一个由 $n$ 个互不相同的整数 $1$ 到 $n$ 以任意顺序组成的数组。例如，$[5, 1, 3, 2, 4]$ 是一个排列，但 $[2, 1, 1]$ 不是排列（因为 $1$ 在数组中出现了两次），$[1, 3, 2, 5]$ 也不是排列（因为 $n = 4$，但数组中出现了 $5$）。 在 BrMeast 视频拍摄失败后，Alex 陷入了抑郁。即使是他的生日也没有让他开心起来。然而，在收到 Timofey 的礼物后，Alex 的心情突然变好了。现在他整天都在玩这份礼物。最近，他想出了一个不同寻常的娱乐方式。 Alex 用他的积木搭建了一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$，根节点为顶点 $1$。然后他将 $1$ 到 $n$ 的每个整数按某种顺序写下来，得到一个排列 $p$。接着，Alex 想出了 $q$ 个三元组 $l, r, x$。对于每个三元组，他尝试判断在顶点 $p_l, p_{l+1}, \ldots, p_r$ 中，是否至少存在一个是顶点 $x$ 的后代。 如果满足 $\mathrm{dist}(1, v) + \mathrm{dist}(v, u) = \mathrm{dist}(1, u)$，则称顶点 $u$ 是顶点 $v$ 的后代，其中 $\mathrm{dist}(a, b)$ 表示顶点 $a$ 和 $b$ 之间的距离。换句话说，顶点 $v$ 必须在从根到顶点 $u$ 的路径上。 Alex 把这个娱乐方式告诉了 Zakhar。现在 Alex 会告诉他的朋友 $q$ 个如上所述的三元组，希望 Zakhar 能帮他判断是否存在后代。Zakhar 很困，所以他向你求助。请帮助 Zakhar 回答所有 Alex 的问题，让他能早点睡觉。

输入的第一行包含一个整数 $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$ 每个整数恰好出现一次）。 接下来 $q$ 行，每行描述 Alex 的一个问题。第 $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" 都会被识别为正答）。

由 ChatGPT 4.1 翻译