luogu#P5649. Sone1

Sone1

题目描述

给你一棵 nn 个节点的有根树,点带权,有 qq 次操作,分为十二种:

  • 0 x y 表示将 xx 的子树中所有点权都改为 yy
  • 1 x 表示把树根换为 xx 节点;
  • 2 x y z 表示把 xxyy 简单路径上所有点权改为 zz
  • 3 x 表示询问 xx 的子树中最小权值;
  • 4 x 表示询问 xx 的子树中最大权值;
  • 5 x y 表示将 xx 的子树中所有点权都增加 yy
  • 6 x y z 表示将 xxyy 简单路径上所有点权加上 zz
  • 7 x y 表示询问 xxyy 简单路径上的最小权值;
  • 8 x y 表示询问 xxyy 简单路径上的最大权值;
  • 9 x y 表示把 xx 的父亲换为 yy,若 yyxx 的子树里则忽略此操作;
  • 10 x y 表示询问 xxyy 简单路径上的点权和;
  • 11 x 表示询问 xx 的子树中点权和。

输入格式

第一行两个正整数 n,qn,q,表示节点数与操作数。
接下来 n1n-1 行,每行两个正整数 u,vu,v,表示 uuvv 之间有一条边。
然后 nn 行,每行一个整数表示点权。
后面一行一个正整数表示初始的根。
最后 qq 行,每行若干个正整数,表示一次操作。

输出格式

对于每个 3,4,7,8,10,113,4,7,8,10,11 操作,输出一行一个整数表示答案。

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
9
1
1
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
173
860
103
791
608
1557

提示

来源:BZOJ 3153

【数据范围】

对于 100%100\% 的数据,1n,m1051\le n,m \le 10^5,中间计算的所有值在 [231,231)[-2^{31},2^{31}) 范围内。
由于本题过于难写,可以点击 这里 下载测试数据,本地通过后再提交。