关于树剖(单点修改,链上查询最小值)
  • 板块学术版
  • 楼主Prean
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/6/7 17:42
  • 上次更新2023/11/7 01:01:31
查看原帖
关于树剖(单点修改,链上查询最小值)
160839
Prean楼主2020/6/7 17:42

请问这个树剖写的有问题吗?求指教QwQ

int min(const int x,const int y){
	return x>y?y:x;
}
void DFS1(int u){
	d[u]=d[f[u]]+1;
	for(auto v:G[u])if(v!=f[u]){
		f[v]=u;DFS1(v);
		if(s[v]>s[son[u]])son[u]=v;
		s[u]+=s[v];
	}
	++s[u];
}
void DFS2(int u,int tp){
	top[u]=tp;
	id[u]=++dfc;rnk[dfc]=u;
	if(!son[u])return;
	DFS2(son[u],tp);
	for(auto v:G[u])if(v!=f[u]&&v!=son[u]){
		DFS2(v,v);
	}
}
void build(){
	int i;
	for(N=1;N<=n+1;N<<=1);
	for(i=1;i<=n;++i){
		zkw[i+N]=val[rnk[i]];
	}
	for(i=N-1;i;--i){
		zkw[i]=min(zkw[i<<1],zkw[i<<1|1]);
	}
}
void modify(int x,int v){
	zkw[x+=N]=v;
	for(x>>=1;x;x>>=1){
		zkw[x]=min(zkw[x<<1],zkw[x<<1|1]);
	}
}
int query(int s,int t){
	int ans=0x7fffffff;
	for(s+=N-1,t+=N+1;s^t^1;s>>=1,t>>=1){
		if(~s&1)ans=min(ans,zkw[s^1]);
		if(t&1)ans=min(ans,zkw[t^1]);
	}
	return ans;
}
int ask(int x,int y){
	int ans=0x7fffffff;
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])x^=y^=x^=y;
		ans=min(ans,query(id[top[x]],id[x]));
		x=f[top[x]];
	}
	if(d[x]>d[y])x^=y^=x^=y;
	ans=min(ans,query(id[x],id[y]));
	return ans;
}
2020/6/7 17:42
加载中...