区间完美匹配

时间限制：$2$ 秒。内存限制：$512$ MB。

题目描述

给定一棵有 $n$ 个顶点的树，顶点编号为 $1,2,\ldots,n$，顶点 $v$ 的权值为整数 $a_v$。

给定 $q$ 个询问，每个询问包含两个整数 $L,R$。删除所有满足 $L\le a_v\le R$ 的顶点，以及与这些顶点相连的边，判断剩余森林是否存在完美匹配。

匹配是一个边集，其中任意两条边没有公共端点。如果剩余的每个顶点都恰好属于一条匹配边，则称其为完美匹配。约定空森林存在完美匹配。

各个询问相互独立，每次都是在原树基础上删除满足 $L\le a_v\le R$ 的顶点。

输入格式

输入文件：forest.in。

第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树的一条边。

接下来 $q$ 行，每行包含两个整数 $L,R$，表示一个询问。

输出格式

输出文件：forest.out。

对每个询问，输出一行。如果剩余森林存在完美匹配，输出 $\texttt{Yes}$；否则输出 $\texttt{No}$。

样例

输入：

4 4
1 2 3 4
1 2
2 3
3 4
2 3
1 2
1 4
5 5

输出：

No
Yes
Yes
Yes

样例解释

第一个询问留下两个孤立顶点，不存在完美匹配。第二个询问留下边 $\{3,4\}$，这条边构成完美匹配。第三个询问删除全部顶点，按约定答案为 $\texttt{Yes}$。第四个询问没有删除顶点，可以选择边 $\{1,2\}$ 和 $\{3,4\}$。

附加样例 $\texttt{forest2.in/.ans}$、$\texttt{forest3.in/.ans}$、$\texttt{forest4.in/.ans}$、$\texttt{forest5.in/.ans}$ 分别满足测试点 $3\sim6$、$10\sim12$、$13\sim14$、$17\sim20$ 的限制。

数据范围

对于所有测试点，$1\le n,q\le10^5$，$-10^9\le a_v,L,R\le10^9$，$L\le R$，$1\le u,v\le n$。输入的 $n-1$ 条边构成一棵树，所有输入数值均为整数。

特殊性质 $A$：存在一个顶点与其他所有顶点直接相连。

特殊性质 $B$：对于每个顶点 $v$，都有 $a_v\in\{0,1\}$。