有关我遍历整棵树的一个疑惑
查看原帖
有关我遍历整棵树的一个疑惑
626785
lxc_awa楼主2024/3/17 21:55

本代码线段树操作未测试，针对dfs1和dfs2的疑惑 为什么将vector从正序遍历改成倒序遍历就能正确初始化信息

code1

#include<bits/stdc++.h>
#define int long long
#define lc p*2
#define rc p*2+1
using namespace std;
const int n=1e5+7;
int fa[n],son[n],rpos[n],pos[n],dep[n],siz[n],top[n],val[n],tot;
vector<int> vec[n];
struct tree{
	int l,r,num,tag;
	int first,back;
}seg[n];
int a,b;
char op;
int x,y,z;
int l1,l2;
void dfs1(int u,int f){
	dep[u]=dep[f]+1;
	siz[u]=1;
	fa[u]=f;
	for(int i=0;i<vec[u].size();i++){
		int v=vec[u][i];
		if(v!=f){
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[son[u]]<siz[v]){
				son[u]=v;
			}
		}
	}
}
void dfs2(int u,int t){
	top[u]=t;
	pos[u]=++tot;
	rpos[tot]=u;
	if(son[u]){
		dfs2(son[u],t);
	}
	for(int i=0;i<vec[u].size();i++){
		int v=vec[u][i];
		if(v!=fa[u]&&v!=son[u]){
			dfs2(v,v);
		}
	}
}
void push_tag(int p,int d){
	seg[p].tag=d;
	seg[p].first=d;
	seg[p].back=d;
	seg[p].num=1;
}
void push_up(int p){
	seg[p].num=seg[lc].num+seg[rc].num;
	if(seg[lc].back==seg[rc].first)seg[p].num--;
	seg[p].first=seg[lc].first;
	seg[p].back=seg[rc].back;
}
void push_down(int p){
	if(seg[p].tag!=-1){
		push_tag(lc,seg[p].tag);
		push_tag(rc,seg[p].tag);
		seg[p].tag=-1;
	}
}
void build(int p,int pl,int pr){
	seg[p].l=pl;
	seg[p].r=pr;
	seg[p].tag=-1;
	if(pl==pr){
		seg[p].num=1;
		seg[p].first=val[rpos[pl]];
		seg[p].back=val[rpos[pl]];
		return;
	}
	int mid=(pl+pr)/2;
	build(lc,pl,mid);
	build(rc,mid+1,pr);
	push_up(p);
}
int find_col(int p,int po){
	if(seg[p].l==seg[p].r&&seg[p].l==po){
		return seg[p].first;
	}
	int mid=(seg[p].l+seg[p].r)/2;
	if(po<=mid)return find_col(lc,po);
	if(po>mid)return find_col(rc,po);
}
int query(int p,int ll,int rr){
	if(ll<=seg[p].l&&rr<=seg[p].r){
		return seg[p].num;
	}
	push_down(p);
	int sum=0;
	bool f1=false,f2=false;
	int mid=(seg[p].l+seg[p].r)/2;
	if(ll<=mid)f1=true,sum+=query(lc,ll,rr);
	if(mid<rr)f2=true,sum+=query(lc,ll,rr);
	if(f1&&f2&&seg[lc].back==seg[rc].first)sum--;
	return sum;
}
void update(int p,int ll,int rr,int d){
	if(ll<=seg[p].l&&rr<=seg[p].r){
		push_tag(p,d);
		return;
	}
	push_down(p);
	int mid=(seg[p].l+seg[p].r)/2;
	if(ll<=mid)update(lc,ll,rr,d);
	if(mid<rr)update(lc,ll,rr,d);
	push_up(p);
}
int query(int ll,int rr){
	int fl=top[ll],fr=top[rr];
	int prel=-1,prer=-1;
	int sum=0;
	while(fl!=fr){
		if(dep[fl]<dep[fr])swap(fl,fr),swap(ll,rr),swap(prel,prer);
		int col1=find_col(1,pos[ll]);
		int col2=find_col(1,pos[fl]);
		sum+=query(1,pos[fl],pos[ll]);
		if(col1==prel){
			sum--;
		}
		prel=col2;
		ll=fa[fl];
		fl=top[ll];
	}
	if(pos[ll]>pos[rr])swap(ll,rr),swap(prel,prer);
	int col1=find_col(1,pos[ll]);
	int col2=find_col(1,pos[rr]);
	sum+=query(1,pos[ll],pos[rr]);
	if(col1==prel)sum--;
	if(col2==prer)sum--;
	return sum;
}
void update(int ll,int rr,int d){
	int fl=top[ll],fr=top[rr];
	while(fl!=fr){
		if(dep[fl]<dep[fr])swap(fl,fr),swap(ll,rr);
		update(1,pos[fl],pos[ll],d);
		ll=fa[fl];
		fl=top[ll];
	}
	if(pos[ll]>pos[rr])swap(ll,rr);
	update(1,pos[ll],pos[rr],d);
}
signed main(){
	cin>>a>>b;
	for(int i=1;i<=a;i++){
		cin>>val[i];
	}
	for(int i=1;i<a;i++){
		cin>>l1>>l2;
		vec[l1].push_back(l2);
		vec[l2].push_back(l1);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,a);
//	for(int i=1;i<=b;i++){
//		cin>>op;
//		if(op=='C'){
//			cin>>x>>y>>z;
//			update(x,y,z);
//		}
//		else if(op=='Q'){
//			cin>>x>>y;
//			cout<<query(x,y)<<endl;
//		}
//	}
//	for(int i=1;i<=a*3;i++){
//		cout<<seg[i].l<<' '<<seg[i].r<<' '<<seg[i].num;
//		cout<<endl;
//	}
for(int i=1;i<=a*3;i++){
	cout<<seg[i].l<<' '<<seg[i].r<<' '<<seg[i].num<<' '<<seg[i].first<<' '<<seg[i].back<<endl;
}
	return 0;
}

code2

#include<bits/stdc++.h>
#define int long long
#define lc p*2
#define rc p*2+1
using namespace std;
const int n=1e5+7;
int fa[n],son[n],rpos[n],pos[n],dep[n],siz[n],top[n],val[n],tot;
vector<int> vec[n];
struct tree{
	int l,r,num,tag;
	int first,back;
}seg[n];
int a,b;
char op;
int x,y,z;
int l1,l2;
void dfs1(int u,int f){cout<<u<<endl;
	dep[u]=dep[f]+1;
	siz[u]=1;
	fa[u]=f;
	for(int i=vec[u].size()-1;i>=0;i--){
		int v=vec[u][i];
		if(v!=f){
			dfs1(v,u);
			siz[u]+=siz[v];
			if(siz[son[u]]<siz[v]){
				son[u]=v;
			}
		}
	}
}
void dfs2(int u,int t){
	
	top[u]=t;
	pos[u]=++tot;
	rpos[tot]=u;
	if(son[u]){
		dfs2(son[u],t);
	}
	for(int i=vec[u].size()-1;i>=0;i--){
		int v=vec[u][i];
		if(v!=fa[u]&&v!=son[u]){
			dfs2(v,v);
		}
	}
}
void push_tag(int p,int d){
	seg[p].tag=d;
	seg[p].first=d;
	seg[p].back=d;
	seg[p].num=1;
}
void push_up(int p){
	seg[p].num=seg[lc].num+seg[rc].num;
	if(seg[lc].back==seg[rc].first)seg[p].num--;
	seg[p].first=seg[lc].first;
	seg[p].back=seg[rc].back;
}
void push_down(int p){
	if(seg[p].tag!=-1){
		push_tag(lc,seg[p].tag);
		push_tag(rc,seg[p].tag);
		seg[p].tag=-1;
	}
}
void build(int p,int pl,int pr){
	seg[p].l=pl;
	seg[p].r=pr;
	seg[p].tag=-1;
	if(pl==pr){
		seg[p].num=1;
		seg[p].first=val[rpos[pl]];
		seg[p].back=val[rpos[pl]];
		return;
	}
	int mid=(pl+pr)/2;
	build(lc,pl,mid);
	build(rc,mid+1,pr);
	push_up(p);
}
int find_col(int p,int po){
	if(seg[p].l==seg[p].r&&seg[p].l==po){
		return seg[p].first;
	}
	int mid=(seg[p].l+seg[p].r)/2;
	if(po<=mid)return find_col(lc,po);
	if(po>mid)return find_col(rc,po);
}
int query(int p,int ll,int rr){
	if(ll<=seg[p].l&&rr<=seg[p].r){
		return seg[p].num;
	}
	push_down(p);
	int sum=0;
	bool f1=false,f2=false;
	int mid=(seg[p].l+seg[p].r)/2;
	if(ll<=mid)f1=true,sum+=query(lc,ll,rr);
	if(mid<rr)f2=true,sum+=query(lc,ll,rr);
	if(f1&&f2&&seg[lc].back==seg[rc].first)sum--;
	return sum;
}
void update(int p,int ll,int rr,int d){
	if(ll<=seg[p].l&&rr<=seg[p].r){
		push_tag(p,d);
		return;
	}
	push_down(p);
	int mid=(seg[p].l+seg[p].r)/2;
	if(ll<=mid)update(lc,ll,rr,d);
	if(mid<rr)update(lc,ll,rr,d);
	push_up(p);
}
int query(int ll,int rr){
	int fl=top[ll],fr=top[rr];
	int prel=-1,prer=-1;
	int sum=0;
	while(fl!=fr){
		if(dep[fl]<dep[fr])swap(fl,fr),swap(ll,rr),swap(prel,prer);
		int col1=find_col(1,pos[ll]);
		int col2=find_col(1,pos[fl]);
		sum+=query(1,pos[fl],pos[ll]);
		if(col1==prel){
			sum--;
		}
		prel=col2;
		ll=fa[fl];
		fl=top[ll];
	}
	if(pos[ll]>pos[rr])swap(ll,rr),swap(prel,prer);
	int col1=find_col(1,pos[ll]);
	int col2=find_col(1,pos[rr]);
	sum+=query(1,pos[ll],pos[rr]);
	if(col1==prel)sum--;
	if(col2==prer)sum--;
	return sum;
}
void update(int ll,int rr,int d){
	int fl=top[ll],fr=top[rr];
	while(fl!=fr){
		if(dep[fl]<dep[fr])swap(fl,fr),swap(ll,rr);
		update(1,pos[fl],pos[ll],d);
		ll=fa[fl];
		fl=top[ll];
	}
	if(pos[ll]>pos[rr])swap(ll,rr);
	update(1,pos[ll],pos[rr],d);
}
signed main(){
	cin>>a>>b;
	for(int i=1;i<=a;i++){
		cin>>val[i];
	}
	for(int i=1;i<a;i++){
		cin>>l1>>l2;
		vec[l1].push_back(l2);
		vec[l2].push_back(l1);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,a);
//	for(int i=1;i<=b;i++){
//		cin>>op;
//		if(op=='C'){
//			cin>>x>>y>>z;
//			update(x,y,z);
//		}
//		else if(op=='Q'){
//			cin>>x>>y;
//			cout<<query(x,y)<<endl;
//		}
//	}
//	for(int i=1;i<=a*3;i++){
//		cout<<seg[i].l<<' '<<seg[i].r<<' '<<seg[i].num;
//		cout<<endl;
//	}
for(int i=1;i<=a*3;i++){
	cout<<seg[i].l<<' '<<seg[i].r<<' '<<seg[i].num<<' '<<seg[i].first<<' '<<seg[i].back<<endl;
}
	return 0;
}
2024/3/17 21:55