[文章目录]
Description
带修改链上点权的查询子树最小权值并附带更改根节点。
nyd。。。写了一上午。终于拿着对的标程拍出来了。
考虑更改根的两种情况：
1.根在查询节点的子树中。需要将根节点所在的儿子的子树的区间都抠掉，所得的区间即为查询区间。
2.根不在查询节点的子树中，那么直接查询子树。
具体找所在儿子的方法为：
1.查询节点时间戳是否在查询节点内。
2.如果在内是否为查询节点。
3.如果在子树中，将根爬到儿子。具体为：如果和查询节点在一条重链上，答案为查询节点的重儿子。如果不在一条重链上，将其向上爬。如果top的fa为查询节点，那么答案为top，否则为top的fa，递归进行。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 150000
using namespace std;
typedef unsigned int uin;
const uin inf=2147483548ll;
uin n,m,now,root;
uin head[N],nxt[N<<1],to[N<<1],cnt;
void add(uin x,uin y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
uin deep[N],fa[N],siz[N],top[N],son[N],in[N],out[N],tot;
uin tr[N],w[N];
void dfs1(uin x,uin pre)
{
deep[x]=deep[pre]+1;
fa[x]=pre; siz[x]++;
for(uin i=head[x];i;i=nxt[i])
if(to[i]!=pre)
{
dfs1(to[i],x);
siz[x]+=siz[to[i]];
if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
}
}
void dfs2(uin x,uin anc)
{
top[x]=anc; in[x]=++tot; tr[tot]=w[x];
if(son[x]) dfs2(son[x],anc);
for(uin i=head[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
out[x]=tot;
}
uin mi[N<<2],lz[N<<2];
void pushup(uin pos){mi[pos]=min(mi[pos<<1],mi[pos<<1|1]);}
void pushdown(uin pos)
{
if(lz[pos]!=inf)
{
mi[pos<<1]=lz[pos]; lz[pos<<1]=lz[pos];
mi[pos<<1|1]=lz[pos]; lz[pos<<1|1]=lz[pos];
lz[pos]=inf;
}
}
void build(uin pos,uin l,uin r)
{
lz[pos]=inf;
if(l==r) {mi[pos]=tr[l]; return ;}
uin mid=l+r>>1;
build(pos<<1,l,mid); build(pos<<1|1,mid+1,r);
pushup(pos);
}
void fix(uin pos,uin l,uin r,uin x,uin y,uin z)
{
if(x<=l&&y>=r) {mi[pos]=lz[pos]=z; return ;}
uin mid=l+r>>1; pushdown(pos);
if(y<=mid) fix(pos<<1,l,mid,x,y,z);
else if(x>mid) fix(pos<<1|1,mid+1,r,x,y,z);
else fix(pos<<1,l,mid,x,y,z),fix(pos<<1|1,mid+1,r,x,y,z);
pushup(pos);
}
uin query(uin pos,uin l,uin r,uin x,uin y)
{
if(x>y) return inf;
if(x<=l&&y>=r) return mi[pos];
uin mid=l+r>>1; pushdown(pos);
if(y<=mid) return query(pos<<1,l,mid,x,y);
else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
else return min(query(pos<<1,l,mid,x,y),query(pos<<1|1,mid+1,r,x,y));
}
void Fix()
{
uin x,y,z; scanf("%u%u%u",&x,&y,&z);
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
fix(1,1,n,in[top[x]],in[x],z);
x=fa[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
fix(1,1,n,in[x],in[y],z);
}
void Query()
{
uin x; scanf("%u",&x);
if(x==now) {printf("%u\n",mi[1]); return ;}
if(in[now]<in[x]||in[now]>out[x]) {printf("%u\n",query(1,1,n,in[x],out[x])); return ;}
uin y=now; while(fa[y]!=x) y=(top[y]==top[x])?son[x]:(fa[top[y]]==x?top[y]:fa[top[y]]);
printf("%u\n",min(query(1,1,n,1,in[y]-1),query(1,1,n,out[y]+1,n)));
}
int main()
{
scanf("%u%u",&n,&m);
uin i,x,y,sw;
for(i=1;i!=n;++i)
{
scanf("%u%u",&x,&y);
add(x,y); add(y,x);
}
for(i=1;i<=n;++i) scanf("%u",w+i);
scanf("%u",&now);
dfs1(now,0);
dfs2(now,now);
build(1,1,n);
while(m--)
{
scanf("%u",&sw);
switch(sw)
{
case 1: scanf("%u",&now); break;
case 2: Fix(); break;
case 3: Query(); break;
}
}
return 0;
}