← 返回题目

题库练习不寻常的娱乐

← 上一题下一题 →

A6900 | $不寻常的娱乐$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

一棵树是一个无环连通图。 排列是一个由 $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

C++ 编辑器

输入

输出