首页 > 其他分享 >[BZOJ3306] 树

[BZOJ3306] 树

时间:2024-03-18 18:11:19浏览次数:25  
标签:rt minn int tr BZOJ3306 id define

题目

[BZOJ3306] 树

样例输入:

3 7
0 1
1 2
1 3
Q 1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1

样例输出:

1
2
3
4

数据范围

\({n,Q \leq 10^5}\)

分析

\(\color{skyblue}{1}\)

这道题如果没有操作换根
那她就是一道板得不能再板的一道板子题
但是
\(\color{red}{\large 没有如果!}\)
所以这道题她就非常的友[cao]爱[dan]

各种全军覆没↓

\(\color{skyblue}{2}\)

由题意
初始rt(root)=1

所以我们以1为根dfs并建立倍增数组

修改点权就是板子 没什么好说的

如果根换成了rt,要查询x子树内的最小值

那么我们需要分情况讨论:

1)若\({x=rt}\) 则直接输出整棵树的最小值

2)若\({LCA(x,rt) \neq x}\)那么直接输出\({x}\)的子树内的最小值

3)若\({LCA(x,rt)=x}\)那么我们可以把她倒过来看 整棵树除了\({x}\)向下走可以到达\({rt}\)的子树之外全部成了\({x}\)在\({rt}\)为根下的子树,我们把这棵子树中最接近\({x}\)的节点\({y}\)求出,在整个区间中除去\({y}\)在\({1}\)根下子树的范围即可得到答案。

code

Elaina's code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define INF 1000000000
#define mst(a,b) memset(a,b,sizeof(a))
#define Elaina 0
#define lid (id<<1)
#define rid (id<<1|1)
const int N = 1000100;

int read(){
    int a=0;
	char x=getchar();
    while(x<'0'||x>'9')x=getchar();
    while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();
    return a;
}

int n,m,rt;
int head[N],v[N],xv[N],tot,cnt,in[N],out[N],a[N],dep[N],f[N][30];
struct EDGE{
	int nxt,to;
}e[N*2];
struct seg_TREE{
	int l,r,minn;
}tr[N*4];
void build(int id,int l,int r){
	tr[id].l=l;
	tr[id].r=r;
	if(l==r){
		tr[id].minn=xv[l];
		return;
	}
	int mid=(l+r)>>1;
	build(lid,l,mid);
	build(rid,mid+1,r);
	tr[id].minn=min(tr[lid].minn,tr[rid].minn);
}

void changemin(int id,int x,int k){
	if(tr[id].l==tr[id].r){
		tr[id].minn=k;
		return;
	}
	int m=(tr[id].l+tr[id].r)>>1;
	if(x<=m)
		changemin(lid,x,k);
	else
		changemin(rid,x,k);
	tr[id].minn=min(tr[lid].minn,tr[rid].minn);
	return;
} 
int askmin(int id,int l,int r){
	if(l>r){
		return INF;
	}
	if(tr[id].l>=l&&tr[id].r<=r){
		return tr[id].minn;
	}
	int mid=(tr[id].l+tr[id].r)>>1;
	if(r<=mid){
		return askmin(lid,l,r);
	}
	if(l>mid){
		return askmin(rid,l,r);
	}else{
		return min(askmin(lid,l,mid),askmin(rid,mid+1,r));
	}
}
void add_1(int u,int v){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
}

void dfs(int x,int fa){
	xv[++cnt]=a[x];
	in[x]=cnt;
	
	dep[x]=dep[fa]+1;
	f[x][0]=fa;
	
	for(int j=1;j<30;j++){
		f[x][j]=f[f[x][j-1]][j-1];
	}
	for(int i=head[x];i;i=e[i].nxt){
		int k=e[i].to;
		if(k!=fa){
			dfs(k,x);
		}
	}
	out[x]=cnt;
}

signed main(){
	n=read(),m=read();
	int x,y;
	for(int i=1;i<=n;i++){
		x=read(),a[i]=read();
		add_1(x,i);
	}
	rt=1;
	dep[0]=0;
	dfs(rt,0);
//	printf("%lld\n",cnt); 
//	for(int i=1;i<=n;i++){
//		printf("%lld ",xv[i]);
//	}
//	cout<<"\n"; 
	build(1,1,n);
	char s;
	for(int i=1;i<=m;i++){
		cin>>s;
		if(s=='E'){
			x=read();
			rt=x;
		}else if(s=='V'){
			x=read(),y=read();
			changemin(1,in[x],y);
		}else{
			x=read();
			if(x==rt){
				printf("%lld\n",tr[1].minn);
			}else if(in[x]<=in[rt]&&out[x]>=out[rt]){
				int d=dep[rt]-dep[x]-1,y=rt;
				for(int i=0;i<30;i++){
					if(d&(1<<i)){
						y=f[y][i];
					}
				}
				printf("%lld\n",min(askmin(1,1,in[y]-1),askmin(1,out[y]+1,n)));
			}else{
//				printf("%lld %lld\n",in[x],out[x]); 
				printf("%lld\n",askmin(1,in[x],out[x]));
			}
		}
	}
	return Elaina;
} 
/*
3 7
0 1
1 2
1 3
Q 1
V 1 6
Q 1
V 2 5
Q 1
V 3 4
Q 1


5 1000
0 1
1 2
1 3
2 4
2 5
Q 1
E 4
Q 1
*/ 

都看到这了,真的不点个赞吗(>ω<*)

标签:rt,minn,int,tr,BZOJ3306,id,define
From: https://www.cnblogs.com/Elaina-0/p/18081102

相关文章

  • BZOJ3306 树
    记当前根为root,查询的节点为x若x=root,答案即为所有结点的最小值若x与root在1的不同子树中,答案即为x的子树最小值若x与root在1的同一子树中若x在......