刚刚结束

题目描述

给定一棵大小为 $n$ 的无根树，编号为 $i$ 的点初始有点权 $c_i$。

你需要支持两种操作，这两种操作共有 $q$ 个：

• 将编号为 $x$ 的点权改为 $y$。
• 定义一个函数 $\operatorname{f}(u,v,l,r)$，如果我们记此时整棵树中有 $d_i$ 个点的点权为 $i$，连接编号为 $u$ 的点和编号为 $v$ 的点的链上有 $e_i$ 个点（包括链的端点）的点权为 $i$，那么 $\operatorname{f}(u,v,l,r)=\sum\limits_{i=l}^{r} \min(e_i,d_i-e_i)$，由于出题人擅长二分，你只需要输出是否有 $\operatorname{f}(u,v,l,r)\le k$。（保证 $k\in\{0,1\}$）

输入格式

第 $1$ 行包含两个正整数 $n,q$，代表树的大小和操作个数。

第 $2$ 行到第 $n$ 行，每行包含两个正整数 $u,v$，代表树上的一条边。

第 $n+1$ 行包含 $n$ 个正整数，描述数列 $c$。

第 $n+2$ 行到第 $n+q+1$ 行，每行包含 $3$ 或 $6$ 个正整数，形式是 $1\ x\ y$ 或 $2\ u\ v\ l\ r\ k$，描述一次操作。

输出格式

对于每个操作二，输出一行，表示是否有 $\operatorname{f}(u,v,l,r)\le k$，如果是输出 Yes，如果否输出 No。

样例

样例输入1

10 10
1 2
2 3
2 4
2 5
5 6
3 7
2 8
4 9
9 10
3 3 4 4 1 5 1 3 2 3 
1 5 5
1 3 2
2 4 7 4 9 1
1 10 8
2 6 7 2 6 1
1 7 9
1 1 8
1 1 4
2 7 3 8 10 1
2 9 2 5 7 0

样例输出1

Yes
No
Yes
Yes

其余样例在下发文件中。

数据范围

对于 $100\%$ 的数据，满足 $1\le n,q\le 2\times 10^5,1\le u,v,c_i,x,y\le n,1\le l\le r\le n,k\in\{0,1\}$。 $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|} \hline \textbf{Subtask} & \textbf{\textsf{分值}} & {{n\le}} &{{m\le}} & {{k\in}}\cr\hline 1 & 20 & 5000 & 5000 & \{0,1\} \cr\hline 2 & 30 & 10^5 & 10^5 & \{0,1\} \cr\hline 3 & 20 & 2\times 10^5 & 2\times 10^5 & \{0\} \cr\hline 4 & 30 & 2\times 10^5 & 2\times 10^5 & \{0,1\} \cr\hline \end{array} $$

后记

本场比赛的题目名称来自《熊出没》主题曲：

冬眠假期刚刚结束

我还有点糊涂

鸟儿在头顶把森林叫醒

春天空气让我很舒服

天上太阳已红扑扑

看起来很模糊

远处山坡有几棵小树

去年冬眠前我没记住

青草香 浆果甜

喝着露水靠着树

抬起头 踮脚尖

加快我长大的脚步

吹口哨 哼着歌

摇摇晃晃找到路

晃脑袋 揉眼睛

长大的我还有点小糊涂