```cpp
// hzoi.H. 遥远的国度
// https://www.luogu.com.cn/blog/beretty/solution-p3979
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
#define ls u<<1
#define rs u<<1|1
typedef long long LL;
const int N = 1e6 + 10;
struct SegmentTree {
int l,r;
LL mn,cov;
} t[N<<3];
int n,m,head[N],to[N<<1],nxt[N<<1];
LL val[N];
int root,fa[N][21],dep[N],size[N],son[N],num,id[N],raw[N],top[N];
int lg[N];
inline void addedge(int u, int v, int cnt) {
to[cnt] = v;
nxt[cnt] = head[u];
head[u] = cnt;
return;
}
void dfs(int u, int f) {
fa[u][0] = f;
dep[u] = dep[f] + 1;
size[u] = 1;
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if( v == f ) continue;
dfs(v, u);
size[u] += size[v];
if( size[v] > size[son[u]] )
son[u] = v;
}
return;
}
void DFS(int u, int t) {
top[u] = t;
id[u] = ++num;
raw[num] = u;
if( !son[u] ) return;
DFS(son[u], t);
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if( v == fa[u][0] || v == son[u] ) continue;
DFS(v, v);
}
return;
}
void build(int u, int l, int r) {
t[u].l = l, t[u].r = r;
if( l == r ) {
t[u].mn = val[raw[l]];
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid+1, r);
t[u].mn = min(t[ls].mn, t[rs].mn);
return;
}
inline void spread(int u) {
if( !t[u].cov ) return;
t[ls].mn = t[ls].cov = t[rs].mn = t[rs].cov = t[u].cov;
t[u].cov = 0;
return;
}
void cover(int u, int l, int r, LL d) {
if( l <= t[u].l && t[u].r <= r ) {
t[u].mn = t[u].cov = d;
return;
}
spread(u);
if( l <= t[ls].r )
cover(ls, l, r, d);
if( t[rs].l <= r )
cover(rs, l, r, d);
t[u].mn = min(t[ls].mn, t[rs].mn);
return;
}
LL query(int u, int l, int r) {
if( l <= t[u].l && t[u].r <= r ) return t[u].mn;
spread(u);
if( r <= t[ls].r ) return query(ls, l, r);
else if( t[rs].l <= l ) return query(rs, l, r);
else return min(query(ls, l, r), query(rs, l, r));
}
inline void change(int x, int y, LL z) {
while( top[x] ^ top[y] ) {
if( dep[top[x]] > dep[top[y]] )
swap(x, y);
cover(1, id[top[y]], id[y], z);
y = fa[top[y]][0];
}
if( dep[x] > dep[y] )
swap(x, y);
cover(1, id[x], id[y], z);
return;
}
inline int lca(int x, int y) {
if( dep[x] > dep[y] )
swap(x, y);
for(int i = lg[dep[y]-dep[x]]; i >= 0; i--) {
if( dep[x] <= dep[fa[y][i]] )
y = fa[y][i];
}
if( x == y ) return x;
for(int i = lg[dep[x]]; i >= 0; i--) {
if( fa[x][i] ^ fa[y][i] )
x = fa[x][i], y = fa[y][i];
}
return fa[x][0];
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i < n; i++) {
int x,y;
scanf("%d%d",&x,&y);
addedge(x, y, (i<<1)-1);
addedge(y, x, i<<1);
}
for(int i = 1; i <= n; i++) scanf("%d",&val[i]);
dfs(1, 0);
DFS(1, 1);
build(1, 1, n);
for(int i = 1; i <= n; i++)
lg[i] = log2(i) + 1;
for(int i = 1; i <= 20; i++) {
for(int j = 1; j <= n; j++)
fa[j][i] = fa[ fa[j][i-1] ][i-1];
}
scanf("%d",&root);
while( m-- ) {
int opt,x;
scanf("%d%d",&opt,&x);
if( opt == 1 )
root = x;
else if( opt == 2 ) {
int y;
LL z;
scanf("%d%lld",&y,&z);
change(x, y, z);
} else if( opt == 3 ) {
if( root == x )
printf("%lld\n",t[1].mn);
else {
if( lca(x, root) ^ x )
printf("%lld\n",query(1, id[x], id[x]+size[x]-1) );
else {
// 也可求第k个祖先
int anc;
for(int i = head[x]; i; i = nxt[i]) {
anc = to[i];
if( id[anc] <= id[root] && id[root] <= id[anc]+size[anc]-1 ) break;
}
printf("%lld\n",min(query(1, 1, id[anc]-1), query(1, id[anc]+size[anc], n)) );
}
}
}
}
return 0;
}
/*
3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1
1
2
3
4
*/
```
求助
by 401rk8 @ 2020-08-13 15:38:57
opt=3中root在x子树中时需要判断id[anc]+size[anc]<=n
by djh233 @ 2021-01-22 10:05:17
@[djh233](/user/119042) 谢谢
by 401rk8 @ 2021-02-10 12:41:23