[POI] II. Trees

題目連結:http://main.edu.pl/en/archive/oi/2/drz

---

不難發現其實就照著他說的插入就好，不過因為我寫不太出來該如何判斷往哪邊插跟何時要開點，所以我用另外一種寫法。每次都把最大且相鄰的兩個點合併起來成為一個新節點，而當有人找不到人配時就是不合法的。構造完完整的樹後就直接DFS輸出他要的結果即可。

#include <bits/stdc++.h>
using namespace std;
#define N 2500

struct lNode{
	lNode *l, *r;
	int next, dep;
	lNode(){l=NULL;r=NULL;}
};
lNode *List[N+5], __nn[4*N];
lNode* nNode(){
	static int __cnt=0;
	return &__nn[__cnt++];
}
void dfs2(lNode*);
int id=0;
void dfs1(lNode*);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=0;i<n;i++)List[i]=nNode();
	for(int i=0;i<n;i++)List[i]->next=i+1;
	List[n-1]->next=n-1;
	int mx=-1;
	for(int i=0;i<n;i++){
		cin>>(List[i]->dep);
		mx=max(mx, List[i]->dep);
	}
	bool flag=1;
	for(int i=mx;i>=1;i--){
		if(!flag)break;
		for(int j=0,k=0;k<n;j=List[j]->next,k++){
			if(List[j]->dep == i){
				if(List[j]->next==j || List[List[j]->next]->dep != i){
					flag=0;
					break;
				}else{
					int nn = List[j]->next;
					lNode* nnn = nNode();
					nnn->l=List[j];
					nnn->r=List[nn];
					nnn->next=List[nn]->next;
					nnn->dep=List[j]->dep-1;
					List[j] = nnn;
					n--;
				}
			}
		}
	}
	if(flag){
		cout<<id++;
		dfs1(List[0]);
		cout<<'\n';
		dfs2(List[0]);
		cout<<'\n';
	}else{
		cout<<"NIE\n";
	}
	return 0;
}

void dfs2(lNode *rr){
	cout<<"(";
	if(rr->l)dfs2(rr->l);
	if(rr->r)dfs2(rr->r);
	cout<<")";
}

void dfs1(lNode *rr){
	int cur=id++;
	if(rr->l){
		cout<<" "<<cur;
		dfs1(rr->l);
	}
	if(rr->r){
		cout<<" "<<cur;
		dfs1(rr->r);
	}
}