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 1Sample 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。
题目分析：
题目大意：给定一棵有根树，每个点有一个权值，提供三种操作：
1.将x节点变为根节点
2.将x到y路径上的点的权值全部改为v
3.询问x的子树中点权的最小值
这题如果没有换根就是一裸的树链剖分 但是有换根的话 deep number 等性质都会变
我们不妨先按最开始的根进行剖分，然后进行讨论
令L=lca(root,x)
1.root=x 显然，这是我们应该查询整棵树的最小值
2.L!=x 这时直接查询x的整棵子树就行了
3.L=x 随手画一下，我们会发现这时x所管辖的区间是非root链的区间
即与root相连的那个儿子及其子树的补集。直接维护就行了
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int net[500000],to[500000],head[500000];
int deep[500000],fa[500000],number[500000];
int son[500100],size[500000],top[500000];
int v[500100],val[500100],lat[500100];
int cnt,tot;
struct your
{
int x,y;
int minn;
int add;
}a[500000];
void add(int x,int y)
{
net[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
void dfs(int x,int temp)
{
fa[x]=temp;
deep[x]=deep[temp]+1;
size[x]=1;
for(int i=head[x];i;i=net[i])
if(to[i]!=temp)
{
dfs(to[i],x);
size[x]+=size[to[i]];
if(size[son[x]]<size[to[i]]) son[x]=to[i];
}
}
void dfs2(int x,int temp)
{
number[x]=lat[x]=++cnt;
top[x]=temp;
val[number[x]]=v[x];
if(son[x]) dfs2(son[x],temp),lat[x]=max(lat[son[x]],lat[x]);
for(int i=head[x];i;i=net[i])
if(to[i]!=son[x]&&to[i]!=fa[x])
dfs2(to[i],to[i]),lat[x]=max(lat[x],lat[to[i]]);
}
int root;
void pushdown(int num)
{
a[num<<1].add=a[num].add;
a[num<<1|1].add=a[num].add;
a[num<<1].minn=a[num].add;
a[num<<1|1].minn=a[num].add;
a[num].add=0;
}
void build(int dx,int dy,int num)
{
a[num].x=dx,a[num].y=dy;
if(dx==dy)
{
a[num].minn=val[dx];
return ;
}
int mid=(a[num].x+a[num].y)>>1;
build(dx,mid,num<<1);
build(mid+1,dy,num<<1|1);
a[num].minn=min(a[num<<1].minn,a[num<<1|1].minn);
return ;
}
void update(int dx,int dy,int c,int num)
{
if(a[num].x==dx&&a[num].y==dy)
{
a[num].add=c;
a[num].minn=c;
return;
}
if(a[num].add) pushdown(num);
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) update(dx,dy,c,num<<1|1);
else if(dy<=mid) update(dx,dy,c,num<<1);
else
{
update(dx,mid,c,num<<1);
update(mid+1,dy,c,num<<1|1);
}
a[num].minn=min(a[num<<1].minn,a[num<<1|1].minn);
return ;
}
void change(int x,int y,int c)
{
while(top[x]!=top[y])
{
if(deep[top[x]]<=deep[top[y]]) swap(x,y);
update(number[top[x]],number[x],c,1);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
update(number[x],number[y],c,1);
}
int ask(int dx,int dy,int num)
{
if(a[num].x==dx&&a[num].y==dy)
return a[num].minn;
if(a[num].add) pushdown(num);
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) return ask(dx,dy,num<<1|1);
if(dy<=mid) return ask(dx,dy,num<<1);
return min(ask(dx,mid,num<<1),ask(mid+1,dy,num<<1|1));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
scanf("%d",&root);
dfs(root,0);
dfs2(root,root);
build(1,n,1);
for(int i=1;i<=m;i++)
{
int tmp;
scanf("%d",&tmp);
if(tmp==3)
{
int x;
scanf("%d",&x);
if(x==root) printf("%d\n",a[1].minn);
else if(number[x]>number[root]||number[root]>lat[x])
printf("%d\n",ask(number[x],lat[x],1));
else
{
int nmp;
for(int j=head[x];j;j=net[j])
if(to[j]!=fa[x]&&number[root]>=number[to[j]]&&lat[to[j]]>=number[root])
{
nmp=to[j];
break;
}
int ans=0x7f7f7f7f;
if(number[nmp]>=2)ans=min(ans,ask(1,number[nmp]-1,1));
if(lat[nmp]<n) ans=min(ans,ask(lat[nmp]+1,n,1));
printf("%d\n",ans);
}
}
else if(tmp==2)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
change(x,y,c);
}
else scanf("%d",&root);
}
}
