题目描述
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的操作，输出一行代表对应子树的最小点权值。
输入输出样例 输入样例#1：
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：
1 2 3 4
好像除了换根操作之外就是板子
那我们就讲下换根吧
换根 ： 我们分3种情况讨论
1 . 如果now 和 root 重合 ，那就是查询整棵树 ，直接输出tmin[1]就好了
2 . 如果LCA（now，root） != now 这时根与now没有关系，直接查询now的子树即可
3 . 如果LCA（now,root) = now
这时就比较麻烦了
我们可以先找一下now的所有儿子
由于 一个子树的dfs序是连续的
所以 如果这个儿子的id大于等于root
并且这个子树中的最大dfs序（id[son]+size[son]-1）小于等于当前的root
那么就可以判断出root在这个儿子中或者就是这个儿子,记录下这个儿子
还是那句话 ：一个子树的dfs序是连续的
这时now的子树就是去除包含root的那个儿子的子树的整棵树了
然而我讲的并不清楚，要是实在不懂可以手胡一下对吧
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
# define ls now<<1
# define rs now<<1|1
const int M = 100005 ;
const int inf = 2100000000 ;
using namespace std;
inline int read(){
char c=getchar(); int x=0,w=1;
while(c>'9'||c<'0'){if(c=='-') w=-1 ;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
return x*w;
}
int n,m;
struct E{
int nex,to;
}edge[M<<1];
int hea[M],num;
inline void add_edge(int from,int to){
edge[++num].nex=hea[from];
edge[num].to=to;
hea[from]=num;
}
int fa[M],dep[M],size[M],son[M];
int val[M],root;
void dfs1(int u,int father,int deep){
dep[u]=deep;
fa[u]=father;
size[u]=1 ;
int Maxson=-1;
for(int i=hea[u];i;i=edge[i].nex){
int v=edge[i].to;
if(v==father) continue ;
dfs1(v,u,deep+1);
size[u]+=size[v];
if(size[v]>Maxson){
Maxson=size[v];
son[u]=v;
}
}
}
int id[M],cnt,top[M],p[M];
void dfs2(int u,int topf){
top[u]=topf;
id[u]=++cnt;
p[cnt]=val[u];
if(!son[u]) return ;
dfs2(son[u],topf);
for(int i=hea[u];i;i=edge[i].nex){
int v=edge[i].to;
if(!id[v])
dfs2(v,v);
}
}
inline int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<=dep[y]?x:y;
}
int tmin[M<<2],tag[M<<2];
inline void pushup(int now){
tmin[now]=min(tmin[ls],tmin[rs]);
}
inline void pushdown(int now){
if(tag[now]!=-1){
tmin[ls]=tmin[rs]=tag[now];
tag[ls]=tag[rs]=tag[now];
tag[now]=-1;
}
}
void Build(int l,int r,int now){
tag[now]=-1;
if(l==r){
tmin[now]=p[l];
return ;
}
int mid=(l+r)>>1;
Build(l,mid,ls);
Build(mid+1,r,rs);
pushup(now);
}
void change(int L,int R,int C,int l,int r,int now){
if(l==L&&r==R){
tmin[now]=C;
tag[now]=C;
return ;
}
int mid=(l+r)>>1;
pushdown(now);
if(mid>=R) change(L,R,C,l,mid,ls);
else if(mid<L) change(L,R,C,mid+1,r,rs);
else{
change(L,mid,C,l,mid,ls);
change(mid+1,R,C,mid+1,r,rs);
}
pushup(now);
}
void change1(int x,int y,int C){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(id[top[x]],id[x],C,1,n,1);
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change(id[x],id[y],C,1,n,1);
}
int query(int L,int R,int l,int r,int now){
if(l>R||r<L) return inf;
if(l>=L&&r<=R) return tmin[now];
int mid=(l+r)>>1;
pushdown(now);
int Ans=query(L,R,l,mid,ls);
Ans=min(Ans,query(L,R,mid+1,r,rs));
return Ans;
}
int main(){
n=read(); m=read();
int u,v;
for(int i=1;i<n;i++){
u=read(); v=read();
add_edge(u,v);
add_edge(v,u);
}
for(int i=1;i<=n;i++) val[i]=read();
root=read();
dfs1(1,1,1);
dfs2(1,1);
Build(1,n,1);
while(m--){
int opt=read();
if(opt==1){
int x=read();
root=x;
}
else if(opt==2){
int u=read(),v=read(),w=read();
change1(u,v,w);
}
else{
int x=read();
if(x==root) printf("%d\n",tmin[1]);
else{
int lca=LCA(x,root);
if(lca==x){
int y;
for(int i=hea[x];i;i=edge[i].nex){
int v=edge[i].to;
if(id[v]<=id[root]&&id[v]+size[v]-1>=id[root]){
y=v;
break;
}
}
int Ans=query(1,id[y]-1,1,n,1);
Ans=min(Ans,query(id[y]+size[y],n,1,n,1));
printf("%d\n",Ans);
}
else printf("%d\n",query(id[x],id[x]+size[x]-1,1,n,1));
}
}
}
return 0;
}