【问题描述】

​ 一棵以 $1$ 为根的有根树，有黑白两种颜色的点。 令 $1$ 白色，$0$ 黑色。

​ 维护五种操作：

​ $1$.改变一个点的颜色。

​ $2$.使点 $x$ 所在的同色点的导出子图的连通块上每个点加 $val$。

​ $3$.查询 $x$ 同色连通块的点权最大值。

​ $4$.使链 $x,y$ 上所有节点的点权加上 $val$。

​ $5$.使 $x$ 的子树内所有节点的点权加上 $val$。

【输入格式】

​ 第一行两个数 $n,m$ 表示点数和操作数。

​ 接下来 $n-1$ 行每行两个数表示一条树边。

​ 第 $n+1$ 行 $n$ 个数，表示节点初始颜色。

​ 第 $n+2$ 行 $n$ 个数，表示节点的初始值。

​ 接下来 $m$ 行表示每行一个操作。

【输出格式】

​ 对于每个3操作我们输出一个数，表示答案。

【样例输入1】

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

【样例输出1】

17
7

【样例2】

​ 见选手目录下的 $astill/astill2.in$ 与 $astill/astill2.ans$。

【样例3】

​ 见选手目录下的 $astill/astill3.in$ 与 $astill/astill3.ans$。

【样例4】

​ 见选手目录下的 $astill/astill4.in$ 与 $astill/astill4.ans$。

【数据范围及约定】

​ 保证答案在 $int$ 以内。 ​ 测试点 $1\sim 4$ 满足：$n,m\le 1000$； ​ 测试点 $5\sim 8$ 满足：没有操作 $4$ 和 $5$，$n,m\le 200000$； ​ 测试点 $9\sim 12$ 满足：树是链，$n,m\le 200000$； ​ 测试点 $13\sim 16$ 满足：树高不超过 $10$，$n,m\le 200000$； ​ 测试点 $17\sim 20$ 满足：$n,m\le 200000，0\le val \le 100000$。