树剖写错,是该查错还是重写?
  • 板块学术版
  • 楼主_yjh
  • 当前回复14
  • 已保存回复14
  • 发布时间2021/2/20 20:42
  • 上次更新2023/11/5 02:58:21
查看原帖
树剖写错,是该查错还是重写?
222104
_yjh楼主2021/2/20 20:42

Rt,此代码实在查不出错,大佬可不可以帮忙查个错,或者给个建议也可以。

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n,q,_sum,_max,w[30005],nmax[120005],nsum[120005],f[30005],son[30005],d[30005],top[30005],size[30005],rk[30005],id[30005];
vector <int> v[30005];
void Query(int t,int l,int r,int ll,int rr) {
	int mid=(l+r)/2;
	if(l>=ll&&r<=rr) {
		_sum+=nsum[t];
		_max=max(_max,nmax[t]);
		return ;
	}
	if(ll<=mid) Query(2*t,l,mid,ll,rr);
	if(rr>=mid+1) Query(2*t+1,mid+1,r,ll,rr);
}
void Change(int t,int l,int r,int u,int poi) {
	int mid=(l+r)/2;
	if(l==r&&l==u) {
		nmax[t]=poi;
		nsum[t]=poi;
		return ;
	}
	if(rk[u]<=mid) Change(2*t,l,mid,u,poi);
	else Change(2*t+1,mid+1,r,u,poi);
	nmax[t]=max(nmax[2*t],nmax[2*t+1]);
	nsum[t]=nsum[2*t]+nsum[2*t+1];
}
void dfs1(int s,int fa) {
	size[s]=1;
	f[s]=fa;
	d[s]=d[fa]+1;
	for(unsigned int i=0;i<v[s].size();i++) {
		if(v[s][i]!=fa) {
			dfs1(v[s][i],s);
			size[s]+=size[v[s][i]];
			if(size[v[s][i]]>size[son[s]]) {
				son[s]=v[s][i];
			}
		}
	}
}
void dfs2(int s,int fa) {
	if(son[s]) {
		top[son[s]]=top[fa];
		rk[son[s]]=++rk[0];
		id[rk[0]]=son[s];
		dfs2(son[s],s);
	}
	for(unsigned int i=0;i<v[s].size();i++) {
		if(!top[v[s][i]]) {
			top[v[s][i]]=v[s][i];
		    rk[v[s][i]]=++rk[0];
		    id[rk[0]]=v[s][i];
		    dfs2(v[s][i],s);
		}
	}
}
void Build(int t,int l,int r) {
	int mid=(l+r)/2;
	if(l==r) {
		nmax[t]=w[id[t]];
		nsum[t]=w[id[t]];
		return ;
	}
	Build(2*t,l,mid);
	Build(2*t+1,mid+1,r);
	nmax[t]=max(nmax[2*t],nmax[2*t+1]);
	nsum[t]=nsum[2*t]+nsum[2*t+1];
}
void ask(int x,int y) {
	int fx=top[x],fy=top[y];
	while(fx!=fy) {
		if(d[fx]<d[fy]) {
			swap(fx,fy);
			swap(x,y);
		}
		Query(1,1,n,x,y);
		x=f[fx];
		fx=top[x];
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++) {
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++) cin>>w[i];
	id[0]=id[1]=top[1]=rk[1]=1;
	dfs1(1,0);
	dfs2(1,0);
	cin>>q;
	for(int i=1;i<=q;i++) {
		string team;
		cin>>team;
		if(team=="CHANGE") {
			int u,t;
			cin>>u>>t;
			Change(1,1,n,u,t);
		}
		if(team=="QMAX") {
			int u,v;
			cin>>u>>v;
			Query(1,1,n,u,v);
			cout<<_max<<'\n';
		}
		if(team=="QSUM") {
			int u,v;
			cin>>u>>v;
			Query(1,1,n,u,v);
			cout<<_sum<<'\n';
		}
		_sum=_max=0;
	} 
	return 0;
} 
2021/2/20 20:42
加载中...