题目描述
分析
这道题的难点在于增加了换根操作
如果对于每一次操作都重新剖一遍显然是不现实的
我们不妨先以 (1) 为根节点进行树剖
设当前的根节点为 (rt)
如果我们要查询的节点是 (rt)，直接输出全局最小值
如果我们要查询的节点在 以 (1) 为根时 (rt) 的子树中
那么以 (1) 为根或者以 (rt) 为根结果都是一样的
如果我们要查询的节点不属于以上两种情况，也不在 (1) 到 (rt) 的链上，在其他的支叉上
(rt) 为根或是 (1) 为根还是没有影响，也直接查询
要特殊处理的情况就是查询的节点在 (1) 到 (rt) 的链上
此时我们要找到在这条链上的要查询的节点的儿子节点
要计算的就是除了该节点的子树以外所有节点的贡献
要注意初始的最大值设大一点
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
int h[maxn],tot=1;
struct asd{
int to,nxt;
}b[maxn<<1];
void ad(int aa,int bb){
b[tot].to=bb;
b[tot].nxt=h[aa];
h[aa]=tot++;
}
int fa[maxn][22],siz[maxn],son[maxn],dep[maxn],a[maxn];
void dfs1(int now,int lat){
fa[now][0]=lat;
siz[now]=1;
dep[now]=dep[lat]+1;
for(rg int i=1;(1<<i)<=dep[now];i++){
fa[now][i]=fa[fa[now][i-1]][i-1];
}
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==lat) continue;
dfs1(u,now);
siz[now]+=siz[u];
if(son[now]==0 || siz[u]>siz[son[now]]){
son[now]=u;
}
}
}
int tp[maxn],dfnc,dfn[maxn],rk[maxn];
void dfs2(int now,int top){
tp[now]=top;
dfn[now]=++dfnc;
rk[dfnc]=a[now];
if(son[now]) dfs2(son[now],top);
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(u==fa[now][0] || u==son[now]) continue;
dfs2(u,u);
}
}
int n,m,rt;
struct trr{
int l,r,mmin,laz;
trr(){
laz=2147483647;
l=r=mmin=0;
}
}tr[maxn<<2];
void push_up(int da){
tr[da].mmin=std::min(tr[da<<1].mmin,tr[da<<1|1].mmin);
}
void push_down(int da){
if(tr[da].laz!=2147483647){
tr[da<<1].laz=tr[da].laz;
tr[da<<1|1].laz=tr[da].laz;
tr[da<<1].mmin=tr[da].laz;
tr[da<<1|1].mmin=tr[da].laz;
tr[da].laz=2147483647;
}
}
void build(int da,int l,int r){
tr[da].l=l,tr[da].r=r;
if(tr[da].l==tr[da].r){
tr[da].mmin=rk[l];
return;
}
rg int mids=(tr[da].l+tr[da].r)>>1;
build(da<<1,l,mids);
build(da<<1|1,mids+1,r);
push_up(da);
}
int cx(int da,int l,int r){
if(tr[da].l>=l && tr[da].r<=r){
return tr[da].mmin;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1,nans=2147483647;
if(l<=mids) nans=std::min(nans,cx(da<<1,l,r));
if(r>mids) nans=std::min(nans,cx(da<<1|1,l,r));
return nans;
}
void xg(int da,int l,int r,int val){
if(tr[da].l>=l && tr[da].r<=r){
tr[da].laz=val;
tr[da].mmin=val;
return;
}
push_down(da);
rg int mids=(tr[da].l+tr[da].r)>>1;
if(l<=mids) xg(da<<1,l,r,val);
if(r>mids) xg(da<<1|1,l,r,val);
push_up(da);
}
void xgtree(int xx,int yy,int val){
while(tp[xx]!=tp[yy]){
if(dep[tp[xx]]>dep[tp[yy]]) std::swap(xx,yy);
xg(1,dfn[tp[yy]],dfn[yy],val);
yy=fa[tp[yy]][0];
}
if(dep[xx]>dep[yy]) std::swap(xx,yy);
xg(1,dfn[xx],dfn[yy],val);
}
int get_lca(int xx,int yy){
while(tp[xx]!=tp[yy]){
if(dep[tp[xx]]>dep[tp[yy]]) std::swap(xx,yy);
yy=fa[tp[yy]][0];
}
if(dep[xx]>dep[yy]) std::swap(xx,yy);
return xx;
}
int zhao(int xx,int yy){
rg int now=xx;
for(rg int i=20;i>=0;i--){
if(dep[fa[now][i]]>=dep[yy]+1){
now=fa[now][i];
}
}
return now;
}
void cxtree(int xx){
rg int zx=get_lca(xx,rt),nans=2147483647;
if(xx==rt){
printf("%d
",tr[1].mmin);
} else if(zx==xx){
rg int now=zhao(rt,xx);
if(dfn[now]>=1) nans=std::min(nans,cx(1,1,dfn[now]-1));
if(dfn[now]+siz[now]<=n) nans=std::min(nans,cx(1,dfn[now]+siz[now],n));
printf("%d
",nans);
} else {
printf("%d
",cx(1,dfn[xx],dfn[xx]+siz[xx]-1));
}
}
int main(){
memset(h,-1,sizeof(h));
n=read(),m=read();
rg int aa,bb,cc,dd;
for(rg int i=1;i<n;i++){
aa=read(),bb=read();
ad(aa,bb);
ad(bb,aa);
}
for(rg int i=1;i<=n;i++){
a[i]=read();
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
rt=read();
for(rg int i=1;i<=m;i++){
aa=read();
if(aa==1){
rt=read();
} else if(aa==2){
bb=read(),cc=read(),dd=read();
xgtree(bb,cc,dd);
} else {
bb=read();
cxtree(bb);
}
}
return 0;
}