POI2013 Multidrink

POI
构造

POI2013 Multidrink

题目大意：

给一棵树，输出遍历序列a，要求每一个节点被访问到恰好一次，要求从1号节点出发，结束在n号节点，要求对于所有的$i$,a[i]与a[i+1]的距离小于等于2。

$PS.$ 完全没什么想法，只好去膜题解。在这里先orz Claris，若不是他的题解，我是写不出这题的。

给出Claris的题解链接

题解：

以下的题解引用了Claris的内容

首先把1到n的路径取出来，作为主干。

定义毛毛虫为去掉叶子之后只有一条单链的树。

定义non_trivial的毛毛虫为单链非空的毛毛虫。

对于每一个主干上的点，计算它的非主干部分是否为毛毛虫，如果某一个部分不是毛毛虫，那么肯定无解。

接下来，我们将主干上的点划分为两类：

A: non_trival的毛毛虫不超过一个。

B: non_trival的毛毛虫恰有两个。

同时定义一个点是free的，当且仅当它是单点。

如下图：

img

判断一下是否每一对相邻的B点中间都有free点，且所有的B点前后都有free点，如果没有那么也无解。

接下来，我们沿着主干依次走下来：

(若在主干上，只能遍历A类点，只有不在主干点上时才能遍历B类点，但遍历完后又会回到主干点上。但此时若有一个free点，可以使它从主干上到非主干上。这也就是为什么两个B类点之间必须要有一个free点。并且由于起点终点都在主干上，因而B的前后都要有free点。)

若到了p这一层，并且主干点要求先遍历，且p不是free点：我们遍历p后，依次遍历每一个non_trivial毛毛虫，再遍历每一个triival毛毛虫，遍历完后，我们发现此时只能到下一层的主干点上去。

若到了p这一层，并且主干点要求先遍历，且p是free点：遍历完p后，我们可以跳到下一层的非主干点上，因为这样更优。

若到了p这一层，主干点不要求先遍历，且主干点为A类点：遍历每一个trivial毛毛虫，再遍历non_trivial，最后遍历p，并到下一层的非主干点上。

若到了p这一层，主干点不要求先遍历，且主干点为B类点：先遍历每一个trivial毛毛虫，再遍历一条non_trivial，之后借助主干点的缓冲，遍历另一条non_trivial 。但此时，到下一层只能到主干点上了。

接下来看看如何遍历一条毛毛虫(分两种:先遍历根，后遍历根)

将毛毛虫分层，并且将每层分为叶子节点和非叶子结点，根指的是第一层的非叶子结点。

若先遍历根，那么从1层开始一层一层过去，依次遍历奇数层的非叶子结点和偶数层的叶子节点，再反过来，往1层一层一层回来，依次遍历奇数层的叶子结点和偶数层的非叶子节点。

后遍历根与之相似，把奇偶换一下即可。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include<queue>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define pb push_back
#define sz(x) x.size()
#define all(x) x.begin(),x.end()
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=500001;
int n,head[N],tot_edge;
struct Edge{
	int to,nxt;
}edge[N<<1];
void add_edge(int a,int b){
	edge[tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge++;
}
int tot,dis[N],core[N];
bool used[N];
queue<int>Q;
void SP(){
	Q.push(1);used[1]=1;dis[1]=0;
	while(!Q.empty()){
		int p=Q.front();Q.pop();
		for(int i=head[p];~i;i=edge[i].nxt){
			int to=edge[i].to;
			if(used[to])continue;
			Q.push(to);
			used[to]=true;
			dis[to]=dis[p]+1;
		}
	}memset(used,0,sizeof(used));
}
void path(int p){
	used[p]=true;core[dis[p]+1]=p;
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(dis[to]==dis[p]-1){
			path(to);break;
		}
	}
}
#define NO puts("BRAK"),exit(0)
int son[N],md;
bool is_ok[N];
void dfs(int p,int f,int d){
	is_ok[p]=false;md=max(md,d);
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		is_ok[p]=true;
		dfs(to,p,d+1);
		son[p]+=is_ok[to];
	}
	if(son[p]>=2)NO;
}
struct Branch{
	int id,flag;
	bool operator <(const Branch&tmp)const{
		return flag<tmp.flag;
	}
};
vector<Branch>bra[N];
bool fre[N],state[N];
void manage(int p){
	fre[p]=true;int cnt=0;
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(used[to])continue;
		fre[p]=false;
		md=0;dfs(to,p,0);
		if(md<1)bra[p].pb((Branch){to,0});
		else bra[p].pb((Branch){to,1}),cnt++;
	}
	if(cnt>2)NO;
	else if(cnt==2)state[p]=1;
	else state[p]=0;
}
void init(){
	memset(head,-1,sizeof(head));
	Rd(n);
	for(int i=1,a,b;i<n;i++){
		Rd(a),Rd(b);
		add_edge(a,b);
		add_edge(b,a);
	}
	SP();path(n);tot=dis[n]+1;
	for(int i=1;i<=tot;i++)
		manage(core[i]);
}
vector<int>num;
void find(int p,int f){
	num.pb(p);
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		if(is_ok[to]&&!used[to])find(to,p);
	}
}
int ans[N],allc;
void traverse(int p,int f){
	if(!is_ok[p]){ans[++allc]=p;return;}
	num.clear();find(p,0);
	for(int cas=0;cas<sz(num);cas++){
		int cur=num[cas];
		if(cas%2==f){
			for(int i=head[cur];~i;i=edge[i].nxt){
				int to=edge[i].to;
				if(!is_ok[to]&&!used[to])ans[++allc]=to;
			}
		}else ans[++allc]=cur;
	}
	for(int cas=sz(num)-1;cas>=0;cas--){
		int cur=num[cas];
		if(cas%2==f)ans[++allc]=cur;
		else{
			for(int i=head[cur];~i;i=edge[i].nxt){
				int to=edge[i].to;
				if(!is_ok[to]&&!used[to])ans[++allc]=to;
			}
		}
	}
} 
void solve(){
	bool ok=true;
	for(int i=1;i<=tot;i++){
		int p=core[i];
		if(ok&&state[p]==1)NO;
		if(ok&&!fre[p]){
			ans[++allc]=p;
			sort(all(bra[p]));
			for(int j=sz(bra[p])-1;j>=0;j--)traverse(bra[p][j].id,0);
		}else if(ok&&fre[p]){
			ans[++allc]=p;
			ok=false;
		}else if(!ok&&!state[p]){
			sort(all(bra[p]));
			for(int j=0;j<sz(bra[p]);j++)traverse(bra[p][j].id,1);
			ans[++allc]=p;
		}else{
			sort(all(bra[p]));
			for(int j=0;j<sz(bra[p])-1;j++)traverse(bra[p][j].id,1);
			ans[++allc]=p;
			traverse(bra[p][sz(bra[p])-1].id,0);
			ok=true;
		}
	}
}
void Print(){
	if(ans[allc]!=n)NO;
	for(int i=1;i<=allc;i++)
		printf("%d\n",ans[i]);
}
int main(){
	init();
	solve();
	Print();
	return 0;
}
分享到 评论