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

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

第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为根的子树中的最小防御值。

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

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cctype>using namespace std;#define INF 0x3f3f3f3f#define MAXN 110000#define lch (now<<1)#define rch (now<<1^1)typedef long long qword;#ifdef unix#define LL "%d"#else#define LL "%I64d"#endif  const int BUF_SIZE = 30;char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;#define PTR_NEXT() \{         buf_s ++;         if (buf_s == buf_t)         {                 buf_s = buf;                 buf_t = buf + fread(buf, 1, BUF_SIZE, stdin);         } }#define readint(_n_) \{         while (*buf_s != ‘-‘ && !isdigit(*buf_s))         PTR_NEXT();         bool register _nega_ = false;         if (*buf_s == ‘-‘)         {                 _nega_ = true;                 PTR_NEXT();         }         int register _x_ = 0;         while (isdigit(*buf_s))         {                 _x_ = _x_ * 10 + *buf_s - ‘0‘;                 PTR_NEXT();         }         if (_nega_)         _x_ = -_x_;         (_n_) = (_x_); }int n,m;int val_t[MAXN];//segment_tree{{{struct segt{        int l,r,val;        int tag;}tree[MAXN*4];int ptr[MAXN];void down(int now){        if (tree[now].tag!=INF)        {                tree[lch].val=tree[rch].val=tree[lch].tag=tree[rch].tag=tree[now].tag;                tree[now].tag=INF;        }}void update(int now){        if (tree[now].l==tree[now].r)return ;        tree[now].val=min(tree[lch].val,tree[rch].val);}void build_tree(int now,int l,int r){        tree[now].l=l;        tree[now].r=r;        tree[now].tag=INF;        if (l==r){                ptr[l]=now;                tree[now].val=val_t[l];                return;        }        int mid=(l+r)>>1;        build_tree(lch,l,mid);        build_tree(rch,mid+1,r);        update(now);}/*   void set_val(int pos,int val)   {   pos=ptr[pos];   tree[pos].val=val;   while (pos)   {   update(pos);   pos>>=1;   }   }*/void set_seg(int now,int l,int r,int val){        down(now);        if (tree[now].l==l&&tree[now].r==r)        {                tree[now].val=val;                tree[now].tag=val;                return ;        }        int mid=(tree[now].l+tree[now].r)>>1;        if (r<=mid)        {                set_seg(lch,l,r,val);                update(now);                return ;        }        if (mid<l)        {                set_seg(rch,l,r,val);                update(now);                return ;        }        set_seg(lch,l,mid,val);        set_seg(rch,mid+1,r,val);        update(now);}int query_min(int now,int l,int r){        down(now);        if (tree[now].l==l&&tree[now].r==r)        {                return tree[now].val;        }        int mid;        mid=(tree[now].l+tree[now].r)>>1;        if (r<=mid)        {                return query_min(lch,l,r);        }        if (mid<l)        {                return query_min(rch,l,r);        }        return min(query_min(lch,l,mid),query_min(rch,mid+1,r));}//}}}struct Edge{        int np;        Edge *next;}E[MAXN*2],*V[MAXN];int root,tope=-1;void addedge(int x,int y){        E[++tope].np=y;        E[tope].next=V[x];        V[x]=&E[tope];}int dfn[MAXN],l[MAXN],fa[MAXN],inp[MAXN],oup[MAXN];int depth[MAXN];int cnt=0;int siz_s[MAXN],son[MAXN];int siz_t[MAXN];int top[MAXN];int dfs(int now,int dep){        Edge *ne;        int t;        siz_s[now]=0;        siz_t[now]=1;        depth[now]=dep;        for (ne=V[now];ne;ne=ne->next)        {                if (fa[now]!=ne->np)                {                        fa[ne->np]=now;                        t=dfs(ne->np,dep+1);                        siz_t[now]+=t;                        if (t>siz_s[now])                        {                                siz_s[now]=t;                                son[now]=ne->np;                        }                }        }        return siz_t[now];}void dfs2(int now,int tp){        Edge *ne;        dfn[now]=++cnt;        inp[now]=cnt;        l[cnt]=val_t[now];        top[now]=tp;        if (son[now])dfs2(son[now],tp);        for (ne=V[now];ne;ne=ne->next)        {                if (fa[now]!=ne->np&&son[now]!=ne->np)                {                        dfs2(ne->np,ne->np);                }        }        oup[now]=cnt;}int jump[20][MAXN],topj;void init_lca(){        int i,j;        for (i=1;i<=n;i++)jump[0][i]=fa[i];        bool flag=true;        for (i=1;i<20&&flag;i++)        {                flag=false;                topj=i;                for (j=1;j<=n;j++)                {                        jump[i][j]=jump[i-1][jump[i-1][j]];                        if (jump[i][j]!=root)flag=true;                }        }}void swim(int &x,int l){        int i=0;        while (l)        {                if (l&1)x=jump[i][x];                i++;                l>>=1;        }}int lca(int x,int y){        if (depth[x]<depth[y])        {                swim(y,depth[y]-depth[x]);        }        if (depth[x]>depth[y])        {                swim(x,depth[x]-depth[y]);        }        if (x==y)return x;        for (int i=topj;i>=0;i--)        {                if (jump[i][x]!=jump[i][y])                {                        x=jump[i][x];                        y=jump[i][y];                }        }        return fa[x];}int id;int main(){        freopen("input.txt","r",stdin);        //freopen("output2.txt","w",stdout);        //scanf("%d%d",&n,&m);        readint(n);        readint(m);        int i,j,k,x,y,z;        int a;        for (i=1;i<n;i++)        {                //scanf("%d%d",&x,&y);                readint(x);                readint(y);                addedge(x,y);                addedge(y,x);        }        root=1;        fa[root]=root;        dfs(root,1);        dfs2(root,root);        init_lca();        for (i=1;i<=n;i++)        {                readint(x);                //scanf("%d",&x);                val_t[dfn[i]]=x;        }        build_tree(1,1,cnt);        readint(id);        //scanf("%d",&id);        int opt,ans;        //cout<<"a";        for (i=0;i<m;i++)        {                //scanf("%d",&opt);                readint(opt);                if (opt==1)                {                        //scanf("%d",&id);                        readint(id);                }                if (opt==2)                {                        //scanf("%d%d%d",&x,&y,&z);                        readint(x);                        readint(y);                        readint(z);                        while (top[x]!=top[y])                        {                                if (depth[top[x]]<depth[top[y]])swap(x,y);                                set_seg(1,dfn[top[x]],dfn[x],z);                                x=fa[top[x]];                        }                        if (dfn[x]<dfn[y])                        {                                set_seg(1,dfn[x],dfn[y],z);                        }else                        {                                set_seg(1,dfn[y],dfn[x],z);                        }                }                if (opt==3)                {                        //scanf("%d",&x);                        readint(x);                        if (x==id)                        {                                ans=query_min(1,1,n);                                printf("%d\n",ans);                                continue;                        }                        if (x==root)                        {LABEL2:                                y=id;                                /*    for (j=topj;j>=0;j--)                                    {                                    if (jump[j][y]!=x)                                    {                                    y=jump[j][y];                                    }                                    }*/                                swim(y,depth[y]-depth[x]-1);                                ans=INF;                                if (inp[y]!=1)ans=query_min(1,1,inp[y]-1);                                if (oup[y]!=n)ans=min(ans,query_min(1,oup[y]+1,n));                                printf("%d\n",ans);                                continue;                        }                        if (depth[x]>=depth[id])                        {LABEL1:                                ans=query_min(1,inp[x],oup[x]);                                printf("%d\n",ans);                                continue;                        }                        if (lca(x,id)==x)                        {                                /*        ans=INF;                                        ans=query_min(1,1,inp[x]);                                        if (oup[x]!=n)ans=min(ans,query_min(1,oup[x]+1,n));                                        printf("%d\n",ans);*/                                goto LABEL2;                                continue;                        }else                        {                                goto LABEL1;                        }                }                //            cout<<opt<<" "<<x<<" "<<y<<endl;        }}