问题标题: B4173WA20分代码

见此贴。

#include<bits/stdc++.h>
#define ing long long
using namespace std;
struct node{
	int l,r;
}a[100005];
int T,n,u,v;
int f[100005],cnt;
int pos[100005];
int min_f[100005];
int size[100005];
int dfs(int root){
	if(root==0) return 0;
	f[++cnt]=root;
	pos[root]=cnt;
	return size[root]=dfs(a[root].l)+dfs(a[root].r)+1;
}
signed main(){
	cin>>T;
	while(T--){
        bool flag=1;
        cnt=0;
        memset(f,0,sizeof(f));
        memset(min_f,0,sizeof(min_f));
        memset(pos,0,sizeof(pos));
        memset(size,0,sizeof(size));
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i].l>>a[i].r; 
		}
		dfs(1);
		min_f[n+1]=0x3f3f3f3f;
		for(int i=n;i>=1;i--) min_f[i]=min(min_f[i+1],f[i]);
        int t=0;
		for(int i=1;i<=n;i++){
			if(a[f[i]].r&&a[f[i]].l>a[f[i]].r){
				int tmp=0;
				for(int j=pos[a[f[i]].r];j<=n;j++){
					if(!a[f[j]].l){
						if(tmp&&f[j]>a[f[i]].l){
							break;
						}
						tmp=j;
					}
				}
                if(tmp!=0){
                	for(int j=1;j<=i;j++) cout<<f[j]<<" ";
    				for(int j=pos[a[f[i]].r];j<=tmp;j++) cout<<f[j]<<" ";
    				for(int j=pos[a[f[i]].l];j<pos[a[f[i]].r];j++) cout<<f[j]<<" ";
    				for(int j=tmp+1;j<=n;j++) cout<<f[j]<<" ";
                    flag=0;
    				break;    
                }

			}else if(!a[f[i]].l&&f[i+1]>min_f[i+1]){
                if(f[i+size[f[i+1]]+1]!=min_f[i+1]){
    				for(int j=1;j<=i;j++) cout<<f[j]<<" ";
    				for(int j=pos[min_f[i+1]];j<pos[min_f[i+1]]+size[min_f[i+1]];j++) cout<<f[j]<<" ";
    				for(int j=i+1;j<pos[min_f[i+1]];j++) cout<<f[j]<<" ";
    				for(int j=pos[min_f[i+1]]+size[min_f[i+1]];j<=n;j++) cout<<f[j]<<" ";
                    flag=0;
                    break;    
                }else{
                    int tmp=0;
    				for(int j=i+size[f[i+1]]+1;j<=n;j++){
    					if(!a[f[j]].l){
    						if(tmp&&f[j]>f[i+1]){
    							break;
    						}
    						tmp=j;
    					}
    				}
                    if(tmp!=0){
                    	for(int j=1;j<=i;j++) cout<<f[j]<<" ";
        				for(int j=i+size[f[i+1]]+1;j<=tmp;j++) cout<<f[j]<<" ";
        				for(int j=i+1;j<=i+size[f[i+1]];j++) cout<<f[j]<<" ";
        				for(int j=tmp+1;j<=n;j++) cout<<f[j]<<" ";
                        flag=0;
        				break;    
                    }
                }
			}else if(!a[f[i]].r&&a[f[i]].l){
                if(a[f[i]].l>f[i+size[a[f[i]].l]+1]){
                    int tmp=0;
    				for(int j=i+size[a[f[i]].l]+1;j<=n;j++){
    					if(!a[f[j]].l){
    						if(tmp&&f[j]>a[f[i]].l){
    							break;
    						}
    						tmp=j;
    					}
    				}
                    if(tmp!=0){
        				for(int j=1;j<=i;j++) cout<<f[j]<<" ";
        				for(int j=pos[a[f[i]].l]+size[a[f[i]].l];j<=tmp;j++) cout<<f[j]<<" ";
        				for(int j=pos[a[f[i]].l];j<pos[a[f[i]].l]+size[a[f[i]].l];j++) cout<<f[j]<<" ";
        				for(int j=tmp+1;j<=n;j++) cout<<f[j]<<" ";
                        flag=0;
                        break;             
                    }

                }
            }
		}
        if(flag) for(int i=1;i<=n;i++) cout<<f[i]<<" ";
        cout<<endl;
	}
	return 0;
}

谈睿在2026-03-02 21:55:26追加了内容

采纳第3个回答的人。