树上收益查询

给定一棵有 $n$ 个点的无向树，点的编号为 $1$ 至 $n$，每个点的当前收益为 $+1$ 或 $-1$．你需要依次处理两类操作：

• C x：把点 $x$ 的收益乘以 $-1$．
• Q u v k：沿从 $u$ 到 $v$ 的简单路径（包含两个端点），选取一段连续的点，询问这段点的收益和能否恰好为 $k$．允许不选点，此时收益和为 $0$．

每次查询只需回答是否存在这样的连续片段．允许 $u=v$，此时路径只包含这一个点．

输入格式

第一行输入两个整数 $n,q$，分别表示点数和操作数．

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各点的初始收益，每个数为 $1$ 或 $-1$．

接下来 $n-1$ 行，每行两个整数 $u,v$，表示点 $u,v$ 之间有一条无向边．输入保证这些边构成一棵树．

接下来 $q$ 行，每行是一条上述形式的操作．

输出格式

对每条 Q 操作输出一行，存在满足条件的连续片段则输出 YES，否则输出 NO．

样例 1

3 5
1 -1 1
1 2
2 3
Q 1 3 2
Q 1 3 0
C 2
Q 1 3 2
Q 2 3 -1

NO
YES
YES
NO

第一次查询时路径收益依次为 $1,-1,1$，没有连续片段之和为 $2$．第二次查询可以选择空片段．修改后点 $2$ 的收益为 $1$，所以第三次查询可选择点 $1,2$；最后一次查询的路径收益均为 $1$，不能得到 $-1$．

更多样例

点击下载本题选手目录

• Data/sample1.in 与 Data/sample1.ans：$n=1,q=17$，满足子任务 1．
• Data/sample2.in 与 Data/sample2.ans：$n=q=3000$，满足子任务 1．
• Data/sample3.in 与 Data/sample3.ans：$n=q=200000$，满足子任务 2．
• Data/sample4.in 与 Data/sample4.ans：$n=q=200000$，满足子任务 3．
• Data/sample5.in 与 Data/sample5.ans：$n=q=200000$，该样例无特殊限制．
• Data/sample6.in 与 Data/sample6.ans：$n=9,q=2191$，满足子任务 1．
• Data/sample7.in 与 Data/sample7.ans：$n=q=200000$，满足子任务 3．
• Data/sample8.in 与 Data/sample8.ans：$n=q=200000$，该样例无特殊限制．

这些样例独立于正式评测数据构造；通过下载样例不保证获得对应子任务的分数．

数据范围与子任务

对于所有数据，$1\le n,q\le2\times10^5$，$1\le u,v,x\le n$，$-n\le k\le n$，$a_i\in\{-1,1\}$．

各子任务独立计分；只有通过该子任务的全部测试点才能获得对应分数．表中未列出的限制均与完整数据范围相同．