自动搬运

查看原文

来自洛谷，原作者为

	寒酥 **

搬运于2025-08-24 21:55:10，当前版本为作者最后更新于2018-11-05 12:22:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

树剖换根啊,,zz的我zz的请教lxl,大师拍案大笑,不语,少顷,我大呼:"我是zz!"呵呵,太尴尬了...

• 记当前根为rt,查询节点u,换根无非三种情况:
  • 1:u==rt,return minn[1];
  • 2:u不是rt的祖先,即u不在1->rt这条路径上,无所谓,直接按u为根的子树返回
  • 3:u是rt的祖先,即u在1->rt这条路径上,最特殊的情况

主要就是第3种嘛,其实也很好想

找到路径u->rt上的u的直系儿子v,

就会发现rt为根时,u子树覆盖不到的地方是v及v的子树

那么我们就可以把那一段抠出来,因为**子树的重儿子序一定是连续的嘛!**之后计算剩余部分就可以了

#include<bits/stdc++.h>
#define INF 0x7fffffff
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int N=1e5+5;
int rt,n,m,dep[N],f[N],num[N],son[N],top[N],tpos[N],pre[N],tot,cnt,bj[N<<2],minn[N<<2],first[N],w[N];
struct edge{int nt,to;}e[N<<1];
void add(int u,int v){e[++cnt]=(edge){first[u],v};first[u]=cnt;}
void dfs1(int u,int fa)
{
	num[u]=1;
	for(int i=first[u];i;i=e[i].nt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		f[v]=u,dep[v]=dep[u]+1;
		dfs1(v,u);
		num[u]+=num[v];
		if(num[v]>num[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp,tpos[u]=++tot,pre[tot]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int i=first[u];i;i=e[i].nt)
	{
		int v=e[i].to;
		if(v==f[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
void pushup(int rt){minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);}
void pushdown(int rt)
{
	if(bj[rt])
	{
		bj[rt<<1]=bj[rt<<1|1]=bj[rt];
		minn[rt<<1]=minn[rt<<1|1]=bj[rt];
		bj[rt]=0;
	}
}
void build(int l,int r,int rt)
{
	if(l==r)
	{
		minn[rt]=w[pre[l]];
		return;
	}
	int m=(l+r)>>1;
	build(lson),build(rson);
	pushup(rt);
}
void modify(int l,int r,int rt,int nowl,int nowr,int c)
{
	if(nowl<=l&&r<=nowr)
	{
		minn[rt]=bj[rt]=c;
		return;
	}
	int m=(l+r)>>1;
	pushdown(rt);
	if(nowl<=m) modify(lson,nowl,nowr,c);
	if(nowr>m) modify(rson,nowl,nowr,c);
	pushup(rt);
}
int query(int l,int r,int rt,int nowl,int nowr)
{
	if(nowl<=l&&r<=nowr) return minn[rt];
	int m=(l+r)>>1,ans=INF;
	pushdown(rt);
	if(nowl<=m) ans=min(ans,query(lson,nowl,nowr));
	if(nowr>m) ans=min(ans,query(rson,nowl,nowr));
	pushup(rt);
	return ans;
}
void chain_modify(int u,int v,int w)
{
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		modify(1,n,1,tpos[top[u]],tpos[u],w);
		u=f[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	modify(1,n,1,tpos[u],tpos[v],w);
}
int find(int u)
{
	if(u==rt) return -1;
	if(tpos[u]>=tpos[rt]||tpos[u]+num[u]-1<tpos[rt]) return 0;
	int now=rt;
	while(top[now]!=top[u])
	{
		if(f[top[now]]==u) return top[now];
		now=f[top[now]];
	}
	return son[u];
}
int tree_query(int u)
{
	int bo=find(u);
	if(bo==-1) return minn[1];
	if(bo==0) return query(1,n,1,tpos[u],tpos[u]+num[u]-1);
	else
	{
		int ans=query(1,n,1,1,tpos[bo]-1);
		if(tpos[bo]+num[bo]-1!=n) ans=min(ans,query(1,n,1,tpos[bo]+num[bo],n));
		return ans;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	dfs1(1,0),dfs2(1,1),build(1,n,1);
	scanf("%d",&rt);
	for(int i=1,bo,u,v,w;i<=m;++i)
	{
		scanf("%d",&bo);
		if(bo==1) scanf("%d",&rt);
		if(bo==2) scanf("%d%d%d",&u,&v,&w),chain_modify(u,v,w);
		if(bo==3) scanf("%d",&u),printf("%d\n",tree_query(u));
	}
	return 0;
}