7153: BZOJ3153：Sone1

Sxyz里有一群sx。 在花老师的指导下，每周4都有一个集会活动，俗称“浇水”活动。 为了让花老师开花，这群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行，每行x,y表示x-y有一条边 接下去是N行，每行是一个数字，表示每个点的权值 后面一行表示根 接下来是M行 第一个数字是K K=0 表示子树修改，后面x,y，表示以x为根的子树的点权值改成y K=1 表示换根，后面x，表示把这棵树的根变成x K=2 表示链修改，后面x,y,z，表示把这棵树中x-y的路径上点权值改成z K=3 表示子树询问min，后面x，表示以x为根的子树中点的权值min K=4 表示子树询问max，后面x，表示以x为根的子树中点的权值max K=5 表示子树加，后面x,y，表示x为根的子树中点的权值+y K=6 表示链加，后面x,y,z，表示把这棵树中x-y的路径上点权值改成+z K=7 表示链询问min，后面x,y，表示把这棵树中x-y的路径上点的min K=8 表示链询问max，后面x,y，表示把这棵树中x-y的路径上点的max K=9 表示换父亲，后面x,y，表示把x的父亲换成y，如果y在x子树里不操作。 K=10 表示链询问sum，后面x,y,z，表示表示把这棵树中x-y的路径上点的sum K=11 表示子树询问sum，后面x，表示以x为根的子树的点权sum Output 对于每个询问输出一个答案。 Sample Input Input1: 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   Input2: 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   Sample Output     Output1: 9 1 1 Output2: 173 860 103 791 608 1557       数据范围： N,M<=100000 中间所有的值计算在c++的int内

输出格式

样例输入

样例输出

提示

没有写明提示

题目来源

Sone提供