A93499.不寻常的娱乐

提高+/省选-

官方

通过率：0%

时间限制：1.00s

内存限制：128MB

题目描述

一棵树是一个无环连通图。

排列是一个由 $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$ 。

输出格式

对每个询问：

若存在满足条件的后代，输出 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$ 自己）。
有则 YES，否则 NO。

首页