换根的树剖
https://www.luogu.org/problem/P3979
题意：
（出题人口活好....
给定一棵以 root 为根的 n 个点的有根树，对于任意一个点 x, 给定他
的点权 val。
现在请你完成以下操作
• 1 x 表示把当前有根树的根换为 x
• 2 x y val 表示把从 x 到 y 路径上的点点权设置为 val
• 3 x 询问 x 的子树内（包括 x）点权的最小值，并输出最小值。
分析
我们直接来考虑换根操作：
首先，dfs重新树剖是不现实的。然后，操作2和换根没啥关系，直接做。
所以我们直接考虑操作3，先对点1进行树剖，再设当前的根是root。
-
当x==root：全局最小，直接输出。
-
当x是root在以1为根情况下的子树：谁是根对这个x的子树没有影响
-
x不属于以上情况，但也不在1到root的链上，而在其他的支叉上：还是木有影响，自己手胡以下吧
-
x在1到root的链上：这就是要处理的重点了。
先不管怎么求min，先看看分别该什么时候求min：
1就直接判断完事，2和3性质一样，而且4的条件最好判断（只要lca(x,root)==x即可），所以我们可以先判断4，剩下的就是2或3，即剩下的直接输出
考虑操作4， 在以1为根的情况下，我们如果要求x的子树信息，我们查询的是[in[x], out[x]]这段区间，而在以root为根的情况下，我们如果要求x的子树信息，那我们没有求的是那一段？ 是x在root方向上的亲儿子及其子树。所以我们只需要找到这个亲儿子（我把它形象的成为最近公共儿子lcs）， 然后查找区间[1, in[lcs]-1] ∪ [out[lcs]+1, n] 的信息即可
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN = 100000+9;
const int MAXM = MAXN<<1;
#define ll long long
#define inf 21474836489
int n,m,root;
struct node{
int deep, size, son, fa, tp ,in, out;
}a[MAXN];
int _clock;
int head[MAXN], cnt;
struct seg{
int y, nxt;
}e[MAXM];
void add_edge(int x, int y) {
e[++cnt].y = y;
e[cnt].nxt = head[x];
head[x] = cnt;
}
void dfs1(int x, int fa) {
a[x].fa = fa;
a[x].deep = a[fa].deep + 1;
a[x].size = 1;
for(int i = head[x]; i; i = e[i].nxt)
if(e[i].y != fa) {
dfs1(e[i].y, x);
a[x].size += a[e[i].y].size;
a[x].son = a[a[x].son].size > a[e[i].y].size ? a[x].son : e[i].y;
}
}
ll arr[MAXN], pos[MAXN];
void dfs2(int x, int tp) {
a[x].tp = tp;
a[x].in = ++_clock;
pos[_clock] = arr[x];
if(a[x].son) dfs2(a[x].son, tp);
for(int i = head[x]; i; i = e[i].nxt)
if(e[i].y != a[x].fa && e[i].y != a[x].son) dfs2(e[i].y, e[i].y);
a[x].out = _clock;
}
struct tree{
ll mi, set;
}tr[MAXN<<2];
void pushup(int o) {tr[o].mi = min(tr[o<<1].mi , tr[o<<1|1].mi);}
void build(int o, int l, int r) {
tr[o].set = -1;
if(l == r) {
tr[o].mi = pos[l];
return ;
}
int mid = (l+r)>>1;
build(o<<1, l, mid);
build(o<<1|1, mid+1, r);
pushup(o);
}
void pushdown(int o) {
if(tr[o].set == -1) return ;
tr[o<<1].mi = tr[o<<1|1].mi = tr[o<<1].set = tr[o<<1|1].set = tr[o].set;
tr[o].set = -1;
}
void optset(int o, int l, int r, int ql, int qr, ll k) {
if(ql <= l && r <= qr) {
tr[o].set = tr[o].mi = k;
return ;
}
int mid = (l+r)>>1;
pushdown(o);
if(ql <= mid) optset(o<<1, l, mid, ql, qr, k);
if(mid < qr) optset(o<<1|1, mid+1, r, ql, qr, k);
pushup(o);
}
ll query(int o, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) return tr[o].mi;
int mid = (l+r)>>1;
pushdown(o);
ll ans = inf;
if(ql <= mid) ans = min(ans, query(o<<1, l, mid, ql, qr));
if(mid < qr) ans = min(ans, query(o<<1|1, mid+1, r, ql, qr));
return ans;
}
void ttt_update(int x, int y, ll z) {
while(a[x].tp != a[y].tp) {
if(a[a[x].tp].deep < a[a[y].tp].deep) swap(x,y);
optset(1, 1, n, a[a[x].tp].in, a[x].in, z);
x = a[a[x].tp].fa ;
}
if(a[x].deep > a[y].deep) swap(x,y);
optset(1, 1, n, a[x].in, a[y].in, z);
}
int lca(int x, int y) {
while(a[x].tp != a[y].tp) {
if(a[a[x].tp].deep < a[a[y].tp].deep) swap(x,y);
x = a[a[x].tp].fa;
}
return a[x].deep < a[y].deep ? x : y;
}
int find_lcs(int x, int y) {//找x到y方向上的亲儿子
int last;
while(a[y].tp != a[x].tp) {
last = a[y].tp;
y = a[a[y].tp].fa;
}
if(y != x) last = a[x].son;
return last;
}
int main() {
scanf("%d%d",&n,&m);
int x,y;
for(int i = 1; i < n; i++) {
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
for(int i = 1; i <= n; i++) scanf("%lld",&arr[i]);
scanf("%d",&root);
dfs1(1, 0);
dfs2(1, 1);
build(1, 1, n);
ll z;
int cmd;
int son;
for(int i = 1; i <= m; i++) {
scanf("%d",&cmd);
if(cmd == 1) {
scanf("%d", &root);
} else if(cmd == 2) {
scanf("%d%d%lld",&x,&y,&z);
ttt_update(x, y, z);
} else {
scanf("%d",&x);
if(x == root) printf("%lld
", tr[1].mi);
else if(lca(x, root) == x) {
son = find_lcs(x, root);
printf("%lld
",min(query(1, 1, n, 1, a[son].in-1), query(1, 1, n, a[son].out+1, n)) );
} else printf("%lld
",query(1, 1, n, a[x].in, a[x].out));
}
}
}