题目描述

SXYZ 里有一群 sx 。

在花老师的指导下，每周四都有一个集会活动，俗称“浇水”活动。为了让花老师开花，这群 sx 都很努力地发言。

一次 XBJ 对树很关心，总想有一道树的好题目。所以大家就开始讨论有什么树的好操作。为了让题目变的简单，花老师开始就规定了是有根树。

何其蛙：子树修改，加一个数什么的，显然是可做的。

DJ：换根不是超开心？

DD：什么子树 $\min,\max$ 也不错啊。

ZZW：链上询问 $\min$ 也放进去吧。

WYK: 链 $\max$ 当然的吧。

XBJ：如果不能换父亲就太无聊了吧。

GY：链加。

Monkey：链上和。

SHJJ：链上修改。

WTD：子树加。

Sone: 在线就不说什么了吧……

…………

最后大家发现有这道题目有点麻烦…… 都懒得写，又由于 sone 最近被 3083的遥远的国度 中 LCT 被 树剖 虐暴了…… 就担任了出题活动……

输入格式

第一行是 $n$ 和 $m$ ，表示有这棵树有 $n$ 个点 $m$ 个询问。

之后 $n-1$ 行，每行 $u,v$ 表示 $u,v$ 之间有一条边。

之后 $n$ 行，每行一个数字，表示该点的权值。

之后一行表示根。

之后 $m$ 行，第一个数字是 $k$ ，表示操作的类型。

$k$	操作	参数	内容
$0$	子树修改	$x,y$	表示以$x$ 为根的子树的点权值改成 $y$
$1$	换根	$x$	表示把这棵树的根变成$x$
$2$	链修改	$x,y,z$	表示把这棵树中$x-y$ 的路径上点权值改成 $z$
$3$	子树询问$\min$	$x$	表示以$x$ 为根的子树中点的权值 $\min$
$4$	子树询问$\max$		表示以$x$ 为根的子树中点的权值 $\max$
$5$	子树加	$x,y$	表示$x$ 为根的子树中点的权值加上 $y$
$6$	链加	$x,y,z$	表示把这棵树中$x-y$ 的路径上点权值改成 $z$
$7$	链询问$\min$	$x,y$	表示把这棵树中$x-y$ 的路径上点的 $\min$
$8$	链询问$\max$		表示把这棵树中$x-y$ 的路径上点的 $\max$
$9$	换父亲		表示把$x$ 的父亲换成 $y$ ，如果 $y$ 在x子树里不操作。
$10$	链询问$\mathrm{sum}$	$x,y,z$	表示表示把这棵树中$x-y$ 的路径上点的 $\mathrm{sum}$
$11$	子树询问$\mathrm{sum}$	$x$	表示以$x$ 为根的子树的点权 $\mathrm{sum}$

输出格式

对于每个询问输出一个答案。

样例输入#1

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

样例输出#1

9
1
1

样例输入#2

10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5

样例输出#2

173
860
103
791
608
1557

数据规模与约定

$n,m \le 10^5$ 保证所有计算中间值在 $[-2^{31},2^{31}-1]$ 范围内。

题目来源

Sone提供