A6900. 不寻常的娱乐
编程题
提高+/省选-
知识点
题目描述
一棵树是一个无环连通图。
排列是一个由 $n$ 个互不相同的整数 $1$ 到 $n$ 以任意顺序组成的数组。
在某次视频拍摄失败后，Welcome24ever 心情很差。后来收到朋友的礼物后，他想出了一个“不寻常的娱乐方式”。
Welcome24ever 用积木搭建了一棵有 $n$ 个点的树，点编号为 $1$ 到 $n$，并规定根是点 $1$。然后他把 $1$ 到 $n$ 的每个整数按某种顺序写下来，得到一个排列 $p$。
接着他提出 $q$ 个询问，每个询问给出三个整数 $l,r,x$：
请判断在点 $p_l,p_{l+1},\ldots,p_r$ 中，是否**至少有一个点**是点 $x$ 的**后代**。
定义：如果对点 $v,u$ 有
$\mathrm{dist}(1,v)+\mathrm{dist}(v,u)=\mathrm{dist}(1,u)$，
则称 $u$ 是 $v$ 的后代（也就是：$v$ 在从根 $1$ 走到 $u$ 的路径上）。
fangz 很困，所以请你帮忙回答这些询问。
排列是一个由 $n$ 个互不相同的整数 $1$ 到 $n$ 以任意顺序组成的数组。
在某次视频拍摄失败后，Welcome24ever 心情很差。后来收到朋友的礼物后，他想出了一个“不寻常的娱乐方式”。
Welcome24ever 用积木搭建了一棵有 $n$ 个点的树，点编号为 $1$ 到 $n$，并规定根是点 $1$。然后他把 $1$ 到 $n$ 的每个整数按某种顺序写下来，得到一个排列 $p$。
接着他提出 $q$ 个询问，每个询问给出三个整数 $l,r,x$：
请判断在点 $p_l,p_{l+1},\ldots,p_r$ 中，是否**至少有一个点**是点 $x$ 的**后代**。
定义：如果对点 $v,u$ 有
$\mathrm{dist}(1,v)+\mathrm{dist}(v,u)=\mathrm{dist}(1,u)$，
则称 $u$ 是 $v$ 的后代（也就是：$v$ 在从根 $1$ 走到 $u$ 的路径上）。
fangz 很困，所以请你帮忙回答这些询问。
输入格式
第一行一个整数 $t$（$1\le t\le 10^4$）表示测试用例数。
每个测试用例：
- 第一行两个整数 $n,q$（$1\le n,q\le 10^5$）
- 接下来 $n-1$ 行，每行两个整数 $u_i,v_i$ 表示树的一条边
- 下一行 $n$ 个整数 $p_1,\ldots,p_n$，表示排列 $p$
- 接下来 $q$ 行，每行三个整数 $l,r,x$ 表示一个询问
保证所有测试用例中 $n$ 的总和与 $q$ 的总和都不超过 $10^5$。
每个测试用例：
- 第一行两个整数 $n,q$（$1\le n,q\le 10^5$）
- 接下来 $n-1$ 行，每行两个整数 $u_i,v_i$ 表示树的一条边
- 下一行 $n$ 个整数 $p_1,\ldots,p_n$，表示排列 $p$
- 接下来 $q$ 行，每行三个整数 $l,r,x$ 表示一个询问
保证所有测试用例中 $n$ 的总和与 $q$ 的总和都不超过 $10^5$。
输出格式
对每个询问：
- 若存在满足条件的后代，输出
- 否则输出
- 若存在满足条件的后代，输出
Yes（大小写不限）- 否则输出
No输入输出样例
输入 #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
说明/提示
## 样例解释
每个询问问的是：在区间 $[l,r]$ 里选到的那些点中，是否有点落在 $x$ 的子树里（包括 $x$ 自己）。
有则
每个询问问的是：在区间 $[l,r]$ 里选到的那些点中，是否有点落在 $x$ 的子树里（包括 $x$ 自己）。
有则
YES，否则 NO。