|
||||||||||
树上询问Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 677 Accepted Submission(s): 188 Problem Description 给定一个大小为 $n$ 的树,第 $i$ 个节点点权为 $p_i$,其中 $p_1,p_2,\ldots,p_n$ 是一个大小为 $n$ 的排列。接下来你要处理 $m$ 次以下两种操作之一: - 给定树上两点 $x$ 和 $y$,交换 $p_x$ 和 $p_y$。 - 给定区间 $[l,r]$,询问是否存在树上两点 $x$ 和 $y$,使得 $x$ 到 $y$ 路径上的点权恰好为 $[l,r]$ 区间内所有整数。 Input 输入第一行包含一个整数 $T$ ($1 \le T \le 20$),表示测试数据的组数。 对于每组测试数据, 输入第一行包含一个整数 $n$ ($1 \le n \le 10^5$),表示树的大小。 输入第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le n$),表示节点的点权。保证 $p$ 是一个大小为 $n$ 的排列。 接下来 $n-1$ 行,每行两个整数 $x_i$, $y_i$ ($1 \le x_i, y_i \le n$),表示存在一条连接节点 $x_i$ 与节点 $y_i$ 的边。保证所有边构成一棵树。 接下来一行输入一个整数 $m$ ($1 \le m \le 10^5$),表示操作的数量。 接下来 $m$ 行表示操作,第 $i$ 次操作为两种操作中的一种: - `$1\ x\ y$` ($1\le x,y \le n$),表示交换节点 $x$ 和 $y$ 的点权。注意, $x$ 和 $y$ **可能相同**。 - `$2\ l \ r$` ($1 \le l \le r \le n$),表示询问的区间。 Output 对于每次操作 $2$,输出一行一个字符串 `Yes` 或 `No` ,分别表示树上存在/不存在满足条件的节点 $x$ 与 $y$。 Sample Input
Sample Output
Source | ||||||||||
|