Description

描述
zcwwzdjn在追杀十分sb的zhx，而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时，守护神RapiD阻拦了zcwwzdjn的去路，他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。

问题是这样的：遥远的国度有n个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题，所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx，所以这个重大的问题就被转交到了你的手上。

Input

第1行两个整数n m，代表城市个数和操作数。
第2行至第n行，每行两个整数 u v，代表城市u和城市v之间有一条路。
第n+1行，有n个整数，代表所有点的初始防御值。
第n+2行一个整数 id，代表初始的首都为id。
第n+3行至第n+m+2行，首先有一个整数opt，如果opt=1，接下来有一个整数id，代表把首都修改为id；如果opt=2，接下来有三个整数p1 p2 v，代表将p1 p2路径上的所有城市的防御值修改为v；如果opt=3，接下来有一个整数 id，代表询问以城市id为根的子树中的最小防御值。

Output


对于每个opt=3的操作，输出一行代表对应子树的最小点权值。

Sample Input

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

Sample Output

1
2
3
4
提示
对于20%的数据，n<=1000 m<=1000。
对于另外10%的数据，n<=100000，m<=100000，保证修改为单点修改。
对于另外10%的数据，n<=100000，m<=100000，保证树为一条链。
对于另外10%的数据，n<=100000，m<=100000，没有修改首都的操作。
对于100%的数据，n<=100000，m<=100000，0<所有权值<=2^31。

Solution

如果没有换根就是个树剖板子，换根显然不能真的去换，可以对当前根进行分类讨论。

1.如果询问的节点x就是当前根，那么输出整棵树的答案即可。

2.如果根在询问的节点x的子树中，那么找出根和节点x之间的那条链上x的儿子（这个用倍增即可处理），询问的答案就是min(query(1,id[y]),query(out[y]+1,n))（如果画张图就能很好的理解了）。

3.对于根不在x的子树内也不是x的情况，根的位置对x的子树没有任何影响，直接查询即可。

然而我习惯的不存重儿子的写法不能直接在第二次dfs的时候处理dfs序...需要重新跑一遍循环，为了这个debug了好几个小时...

#include <bits/stdc++.h>

#define ll long long
#define inf 0x3f3f3f3f
#define il inline
#define int long long 

namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int int
    inline I_int read() {
        I_int x = 0 , f = 1 ; char c = getchar() ;
        while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
        while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
        return x * f ;
    }
    char F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
    }
    #undef I_int

}
using namespace io ;

#define N 200010

int n = read() , m = read() ;
int tot , cnt , head[N] , root ;
struct edge {
    int to , nxt ;
} e[N << 1] ;
int dep[N] , siz[N] , last[N] , id[N] , top[N] , fa[N] , w[N] , a[N] ; 
int f[N][19] , lg2[N] ;

void ins(int u , int v) {
    e[++cnt] = (edge) {v , head[u]} ;
    head[u] = cnt ;
}

void dfs1(int u) {
    siz[u] = 1 ;
    for(int i = head[u] ; i ; i = e[i].nxt) {
        if(e[i].to == fa[u]) continue ;
        fa[e[i].to] = u ; f[e[i].to][0] = u ;
        dep[e[i].to] = dep[u] + 1 ;
        dfs1(e[i].to) ;
        siz[u] += siz[e[i].to] ;
    }
}

void dfs2(int u , int topf) {
    top[u] = topf ;
    id[u] = ++ tot ;
    w[tot] = a[u] ;
    int k = 0 ;
    for(int i = head[u]; i ; i = e[i].nxt) {
        if(e[i].to == fa[u]) continue ;
        if(siz[e[i].to] > siz[k]) k = e[i].to ;
    }
    if(!k) return ;
    dfs2(k , topf) ;
    for(int i = head[u]; i ; i = e[i].nxt) {
        if(e[i].to == fa[u] || e[i].to == k) continue ;
        dfs2(e[i].to , e[i].to) ;
    }
} 

#define rc (rt << 1 | 1)
#define lc (rt << 1)
struct tree {
    int l , r , add , min ;
} t[N<<2] ;

void pushup(int rt) { t[rt].min = std::min(t[lc].min , t[rc].min) ; }

void build(int l , int r , int rt) {
    t[rt].l = l ; t[rt].r = r ; t[rt].min = inf ; int mid = (l + r) >> 1 ;
    if(l == r) {t[rt].min = w[l] ; return ; }
    build(l , mid , lc) ; build(mid + 1 , r , rc) ; pushup(rt) ;
}

#define l t[rt].l
#define r t[rt].r
#define mid ((l+r) >> 1)

void pushdown(int rt) {
    int x = t[rt].add ;
    if(!x) return ; 
    t[lc].min = t[rc].min = t[lc].add = t[rc].add = x ; t[rt].add = 0 ;
}

void upd(int L , int R , int c , int rt) {
    if(L <= l && r <= R) { t[rt].min = c ; t[rt].add = c ; return ; } 
    pushdown(rt) ;
    if(L <= mid) upd(L , R , c , lc) ; if(R > mid) upd(L , R , c , rc) ;
    pushup(rt) ;
}

int query(int L , int R , int rt) {
    if(L <= l && r <= R) return t[rt].min ;
    pushdown(rt) ; int ans = 0 ;
    if(L <= mid) ans = query(L , R , lc) ;
    if(R > mid) ans = ans ? std::min(ans , query(L , R , rc)) : query(L , R , rc) ;
    return ans ;
}

#undef l
#undef r
#undef mid
#undef lc
#undef rc

void S_upd(int x , int y , int val) {
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) std::swap(x , y) ;
        upd(id[top[x]] , id[x] , val , 1) ;
        x = fa[top[x]] ;
     }
     if(id[x] > id[y]) std::swap(x , y) ;
     upd(id[x] , id[y] , val , 1) ;
}

void init() {
    for(int i = 2 ; i <= n ; i ++) lg2[i] = lg2[i>>1] + 1 ;
    for(int j = 1 ; j <= 17 ; j ++) {
        for(int i = 1 ; i <= n ; i ++) {
            f[i][j] = f[ f[i][j - 1] ][j - 1] ;
        }
    }
}

int getf(int x , int FF) {
    for(int i = lg2[dep[x]] ; i >= 0 ; i --) {
        if(dep[f[x][i]] > dep[FF]) x = f[x][i] ;
    }    
    return x ;
}

signed main() {
    int ans , pos ;
    for(int i = 1 ; i < n ; i ++) {
        int u = read() , v = read() ;
        ins(u , v) , ins(v , u) ;
    }
    for(int i = 1 ; i <= n ; i ++) a[i] = read() ;
    root = read() ; dep[root] = 1 ;
    dfs1(root) , dfs2(root , root) , init() , build(1 , n , 1);
    for(int i = 1 ; i <= n ; i ++) last[i] = id[i] + siz[i] - 1 ;
    while(m --) {
        int opt = read() , x = read() , y , val ;
        if(opt == 1) root = x ;
        else if(opt == 2) {
            y = read() , val = read() ;
            S_upd(x , y , val) ;
        }
        else {
            if(root == x) ans = t[1].min ;
            else {
                if(id[x] <= id[root] && last[x] >= last[root]) {
                    ans = (1ll << 60) ; pos = getf(root , x) ;
                    if(id[pos] > 1) ans = query(1 , id[pos] - 1 , 1) ;
                    if(last[pos] < n) ans = std::min(ans , query(last[pos] + 1 , n , 1)) ; 
                } else ans = query(id[x] , last[x] , 1) ;
            }
            outn(ans) ; 
        }
    }
//    for(int i = 1 ; i <= n ; i ++) printf("%d " , id[i]) ; puts("") ;
//    for(int i = 1 ; i <= n ; i ++) printf("%d " , last[i]) ; puts("") ;
}