Sone1
题目描述
给你一棵 $n$ 个节点的有根树,点带权,有 $q$ 次操作,分为十二种:
- `0 x y` 表示将 $x$ 的子树中所有点权都改为 $y$
- `1 x` 表示把树根换为 $x$ 节点
- `2 x y z` 表示把 $x$ 到 $y$ 简单路径上所有点权改为 $z$
- `3 x` 表示询问 $x$ 的子树中最小权值
- `4 x` 表示询问 $x$ 的子树中最大权值
- `5 x y` 表示将 $x$ 的子树中所有点权都增加 $y$
- `6 x y z` 表示将 $x$ 到 $y$ 简单路径上所有点权加上 $z$
- `7 x y` 表示询问 $x$ 到 $y$ 简单路径上的最小权值
- `8 x y` 表示询问 $x$ 到 $y$ 简单路径上的最大权值
- `9 x y` 表示把 $x$ 的父亲换为 $y$,若 $y$ 在 $x$ 的子树里则忽略此操作
- `10 x y` 表示询问 $x$ 到 $y$ 简单路径上的点权和
- `11 x` 表示询问 $x$ 的子树中点权和
输入输出格式
输入格式
第一行两个正整数 $n,q$,表示节点数与操作数。
接下来 $n-1$ 行,每行两个正整数 $u,v$,表示 $u$ 和 $v$ 之间有一条边。
然后 $n$ 行,每行一个整数表示点权。
后面一行一个正整数表示初始的根。
最后 $q$ 行,每行若干个正整数,表示一次操作。
输出格式
对于每个 $3,4,7,8,10,11$ 操作,输出一行一个整数表示答案。
输入输出样例
输入样例 #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
说明
来源:BZOJ 3153
【数据范围】
对于 $100\%$ 的数据,$1\le n,m \le 10^5$,中间计算的所有值在 $[-2^{31},2^{31})$ 范围内。
由于本题过于难写,可以点击 [这里](https://darkbzoj.cc/data/3153.zip) 下载测试数据,本地通过后再提交。