记录编号	611018	评测结果	AAAAAAAAAA
题目名称	[TJOI2011] 树的序	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	0.345 s
提交时间	2026-01-24 11:57:48	内存使用	4.44 MiB

#include<iostream>
#include<stack>
using namespace std;

const int MAXN = 1e5 + 5;
stack<int> stk;
int l[MAXN], r[MAXN];
int a, n;
int in[MAXN], pos[MAXN];

void dfs(int u){
	cout << u << ' ';
	if(l[u]) dfs(l[u]);
	if(r[u]) dfs(r[u]);
}

int main(){
	cin >> n;
	for(int i = 1;i <= n;i ++){
		cin >> a;
		pos[a] = i;
	}
	stk.push(1);
	for(int i = 2;i <= n;i ++){
		int lst = 0;
		while(!stk.empty() && pos[i] < pos[stk.top()]){
			lst = stk.top();
			stk.pop();
		}
		if(stk.empty()){
			l[i] = lst;
		}
		else{
			l[i] = r[stk.top()];
			r[stk.top()] = i;
		}
		stk.push(i);
	}

	int rt = 0;
	for(int i = 1;i <= n;i ++){
		in[l[i]] ++;
		in[r[i]] ++;
	}

	for(int i = 1;i <= n;i ++){
		if(!in[i]){
			rt = i;
			break;
		}
	}

//	cout << rt << '\n';

//	for(int i = 1;i <= n;i ++){
//		cout << i << ": " << l[i] << ' ' << r[i] << '\n';
//	}

	dfs(rt);

	return 0;
}