树 bzoj-3306

题目大意：给定一颗n个节点的树，支持换根、修改点权、查询子树最小值。

注释：$1\le n,q\le 10^5$。

---

想法：

如果没有换根操作，就是$dfs$序+线段树维护区间最小值即可。

加入有换根操作，我们发现对修改操作没影响。

我们只需要判断一下询问的点和当前根的关系即可。

Code：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define ls p<<1

#define rs p<<1|1

#define N 100010

using namespace std;

int to[N<<1],nxt[N<<1],tot,head[N];

int f[21][N],dic[N],re[N],size[N],dep[N],cnt,mn[N<<2],val[N],root;

inline void add(int x,int y) {to[++tot]=y; nxt[tot]=head[x]; head[x]=tot;}

void dfs(int pos,int fa)

{

	dic[pos]=++cnt; re[cnt]=pos; f[0][pos]=fa; for(int i=1;i<=20;i++) f[i][pos]=f[i-1][f[i-1][pos]];

	dep[pos]=dep[fa]+1; size[pos]=1; for(int i=head[pos];i;i=nxt[i]) if(to[i]!=fa)

	{

		dfs(to[i],pos);

		size[pos]+=size[to[i]];

	}

}

int lca(int x,int y)

{

	if(dep[x]<dep[y]) swap(x,y);

	for(int i=20;~i;i--) if(dep[f[i][x]]>=dep[y]) x=f[i][x];

	if(x==y) return x;

	for(int i=20;~i;i--) if(f[i][x]!=f[i][y]) x=f[i][x],y=f[i][y];

	return f[0][x];

}

int get_lca(int x,int y)

{

	if(dep[x]<dep[y]) swap(x,y);

	for(int i=20;~i;i--) if(dep[f[i][x]]>dep[y]) x=f[i][x];

	return x;

}

inline void pushup(int p)

{

	mn[p]=min(mn[ls],mn[rs]);

}

void build(int l,int r,int p)

{

	if(l==r) {mn[p]=val[re[l]]; return;}

	int mid=(l+r)>>1;

	build(l,mid,ls); build(mid+1,r,rs);

	pushup(p);

}

void update(int x,int v,int l,int r,int p)

{

	if(l==r) {mn[p]=v; return;}

	int mid=(l+r)>>1;

	if(x<=mid) update(x,v,l,mid,ls);

	else update(x,v,mid+1,r,rs);

	pushup(p);

}

int query(int x,int y,int l,int r,int p)

{

	if(x<=l&&r<=y) return mn[p];

	int mid=(l+r)>>1,ans=0x7f7f7f7f;

	if(x<=mid) ans=min(ans,query(x,y,l,mid,ls));

	if(mid<y) ans=min(ans,query(x,y,mid+1,r,rs));

	return ans;

}

int main()

{

	int x,y,n,m; scanf("%d%d",&n,&m); char opt[10]; for(int i=1;i<=n;i++)

	{

		scanf("%d%d",&x,&y);

		if(!x) root=i;

		else add(i,x),add(x,i);

		val[i]=y;

	}

	dfs(root,root);

	// for(int i=1;i<=n;i++) printf("%d ",size[i]); puts("");

	build(1,n,1);

	for(int i=1;i<=m;i++)

	{

		scanf("%s%d",opt,&x);

		if(opt[0]=='V')

		{

			scanf("%d",&y); update(dic[x],y,1,n,1);

		}

		else if(opt[0]=='E')

		{

			root=x;

		}

		else

		{

			if(x==root) printf("%d\n",query(1,n,1,n,1));

			else if(lca(x,root)!=x) printf("%d\n",query(dic[x],dic[x]+size[x]-1,1,n,1));

			else

			{

				int y=get_lca(root,x);

				printf("%d\n",min(query(1,dic[y]-1,1,n,1),query(dic[y]+size[y],n,1,n,1)));

			}

		}

	}

	return 0;

}

小结：拟对象考虑问题有奇效。

[bzoj3306]树_dfs序_线段树_倍增lca的相关教程结束。