P5649 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$ 操作，输出一行一个整数表示答案。

来源：BZOJ 3153 【数据范围】 对于 $100\%$ 的数据，$1\le n,q \le 10^5$，中间计算的所有值在 $[-2^{31},2^{31})$ 范围内。 由于本题过于难写，可以点击 [这里](https://darkbzoj.cc/data/3153.zip) 下载测试数据，本地通过后再提交。