#题目描述
zcwwzdjn在追杀十分sb的zhx，而zhx逃入了一个遥远的国度。当zcwwzdjn准备进入遥远的国度继续追杀时，守护神RapiD阻拦了zcwwzdjn的去路，他需要zcwwzdjn完成任务后才能进入遥远的国度继续追杀。
问题是这样的：遥远的国度有n个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候RapiD会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于RapiD无法解决这个问题，所以他拦住了zcwwzdjn希望他能帮忙。但zcwwzdjn还要追杀sb的zhx，所以这个重大的问题就被转交到了你的手上。
#做法
树链剖分&LCA
这里相对于一般的树链剖分多了一个换根操作
分情况讨论
PS：对于换根，ETT不用换根的，对于要换根的题，可以这么考虑，查询u的时候，如果新的根在u的上方，u的子树就是原来那个子树，如果新的根是u，就是整个树，如果新的根v是在u下面，只要找到u到v路径上的第一个结点，也就是u的孩子，u新的子树就是去掉这个点所在子树剩下的那些。
就是这样
作为近期的最后一道树链剖分，嘛，接下来刷什么呢？
#AC Code
效率低到不忍直视
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=100005;
vector<int>e[maxn];
typedef vector<int>::iterator vi;
//--线段树
long long seg[maxn*4],laz[maxn*4];
int segl[maxn*4],segr[maxn*4];
const int ls(const int &x){return x<<1;}
const int rs(const int &x){return x<<1|1;}
//--
//--树链剖分
long long va[maxn],val[maxn];
int pos[maxn],fa[maxn],tp[maxn],sz[maxn],dp[maxn],hs[maxn];
int qu[maxn],qf,qt,pn;
int beg[maxn],end[maxn];
void dfs1(int u)
{
sz[u]=1;
for (vi v=e[u].begin();v!=e[u].end();v++)
{
if (!sz[*v])
{
fa[*v]=u;dp[*v]=dp[u]+1;
dfs1(*v);
sz[u]+=sz[*v];
if (sz[*v]>sz[hs[u]])
hs[u]=*v;
}
}
}
void dfs2(int u,int tp)
{
va[beg[u]=pos[u]=++pn]=val[u];
::tp[u]=tp;
// printf("%d->%lld\n",u,va[pn]);
if (hs[u])
{
dfs2(hs[u],tp);
for (vi v=e[u].begin();v!=e[u].end();v++)
if (!pos[*v])
dfs2(*v,*v);
}
end[u]=pn;
}
//--end
void pushdown(int x)
{
if (laz[x])
{
seg[x]=laz[x];
if (segl[x]<segr[x])
laz[ls(x)]=laz[rs(x)]=laz[x];
laz[x]=0;
}
}
void update(int x)
{
pushdown(x);
if (segl[x]<segr[x])
{
pushdown(ls(x)),pushdown(rs(x));
seg[x]=min(seg[ls(x)],seg[rs(x)]);
}
}
int u,v,n,m;
void build(int x,int l,int r)
{
segl[x]=l;segr[x]=r;
if (l==r)
{
seg[x]=va[l];
return;
}
int mid=(l+r)/2;
if (l<=mid)
build(ls(x),l,mid);
if (r>mid)
build(rs(x),mid+1,r);
update(x);
}
long long query(int x,int l,int r,int ql,int qr)
{
pushdown(x);
if (ql<=l && r<=qr)
return seg[x];
int mid=(l+r)/2;
long long ret=0x3f3f3f3f3f3f3f3fll;
if (ql<=mid)
ret=min(ret,query(ls(x),l,mid,ql,qr));
if (qr>mid)
ret=min(ret,query(rs(x),mid+1,r,ql,qr));
return ret;
}
void edit(int x,int l,int r,int ql,int qr,int c)
{
pushdown(x);
if (ql<=l && r<=qr)
{
laz[x]=c;
pushdown(x);
return;
}
int mid=(l+r)/2;
if (ql<=mid)
edit(ls(x),l,mid,ql,qr,c);
if (qr>mid)
edit(rs(x),mid+1,r,ql,qr,c);
update(x);
}
void edit(int u,int v,int c)
{
while (tp[u]!=tp[v])
if (dp[tp[u]]>dp[tp[v]])
edit(1,1,n,pos[tp[u]],pos[u],c),u=fa[tp[u]];
else
edit(1,1,n,pos[tp[v]],pos[v],c),v=fa[tp[v]];
if (dp[u]<dp[v])
edit(1,1,n,pos[u],pos[v],c);
else
edit(1,1,n,pos[v],pos[u],c);
}
int anc[maxn][25];
int lca(int u,int v)
{
if (dp[u]<dp[v])
swap(u,v);
for (int i=20;i>=0;i--)
if (dp[anc[u][i]]>=dp[v])
u=anc[u][i];
if (u==v)
return u;
for (int i=20;i>=0;i--)
if (anc[u][i]!=anc[v][i])
u=anc[u][i],v=anc[v][i];
return anc[v][0];
}
int root;
long long query(int v)
{
if (v==root)
return query(1,1,n,1,n);
int lca=::lca(v,root);
if (lca==v)
{
long long ret=0x3f3f3f3f3f3f3f3fll;
int t=root;
for (int i=20;i>=0;i--)
if (dp[anc[t][i]]>dp[v])
t=anc[t][i];
if (beg[t]>0)
ret=min(ret,query(1,1,n,1,beg[t]-1));
if (end[t]<n)
ret=min(ret,query(1,1,n,end[t],n));
return ret;
}else
return query(1,1,n,beg[v],end[v]);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++)
scanf("%d%d",&u,&v),e[u].push_back(v),e[v].push_back(u);
for (int i=1;i<=n;i++)
scanf("%lld",&val[i]);
scanf("%d",&root);
dp[1]=1;
dfs1(1);dfs2(1,1);
for (int i=1;i<=n;i++)
anc[i][0]=fa[i];
for (int i=1;i<=20;i++)
for (int j=1;j<=n;j++)
anc[j][i]=anc[anc[j][i-1]][i-1];
build(1,1,n);
int x,v,u;
long long o;
for (int i=1;i<=m;i++)
{
scanf("%d",&x);
if (x==1)
scanf("%d",&u),root=u;
else if (x==2)
scanf("%d%d%lld",&u,&v,&o),edit(u,v,o);
else if (x==3)
scanf("%d",&v),printf("%lld\n",query(v));
}
return 0;
}