题目链接：P3549 [POI2013]MUL-Multidrink
题目大意：给一棵树，每次步伐大小只能为 (1) 或 (2)，要求不重复的遍历 (n) 个节点，且起点为 (1)，终点为 (n)。
题解：首先我们将 (1) 到 (n) 的链拎出来，然后我们发现如果一个点挂了一堆叶子可以暂时先不管它，删去叶子后的每一个节点最多有两棵子树，并且必然应当是毛毛虫（一条链周围挂一堆叶子），如果一个点挂了两个毛毛虫，那么这个点的前面和后面都应当有没有叶子节点的链上点才可以，然后我们就把无解的情况判掉了，接下来只需要根据上面的分类讨论来把构造写出来就可以了。
时间复杂度 (O(n))。
代码：
#include <vector>
#include <cstdio>
#include <algorithm>
const int Maxn=500000;
int n;
int deg[Maxn+5];
int head[Maxn+5],arrive[Maxn<<1|5],nxt[Maxn<<1|5],tot;
std::vector<int> g[Maxn+5];
int pre[Maxn+5];
void add_edge(int from,int to){
arrive[++tot]=to;
nxt[tot]=head[from];
head[from]=tot;
}
int p[Maxn+5],p_len;
namespace Find_P{
int fa[Maxn+5];
void init_dfs(int u){
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
if(v==fa[u]){
continue;
}
fa[v]=u;
init_dfs(v);
}
}
void work(){
init_dfs(1);
int u=n;
while(u!=1){
p[++p_len]=u;
u=fa[u];
}
p[++p_len]=u;
std::reverse(p+1,p+1+p_len);
}
}
bool check(int u,int fa){
int num=0;
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
if(v==fa||deg[v]==1){
continue;
}
if(num>0||!check(v,u)){
return 0;
}
num++;
}
return 1;
}
bool in_line[Maxn+5];
bool no_son[Maxn+5];
int son_num[Maxn+5];
int find_a_son(int u,int t=0){
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
if(!in_line[v]&&v!=t){
return v;
}
}
return -1;
}
int find_a_leaf(int u){
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
if(!in_line[v]&°[v]==1){
return v;
}
}
return find_a_son(u);
}
int ans_lis[Maxn+5],ans_len;
int qu[Maxn+5],qu_t;
int tmp_lis[Maxn<<1|5],tmp_len;
void find_a_line(int u,int fa){
qu[++qu_t]=u;
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
if(v==fa){
continue;
}
if(deg[v]==1){
g[u].push_back(v);
pre[v]=u;
}
else{
find_a_line(v,u);
}
}
}
void add_a_star(int u,int v_1=0,int v_2=0){
for(int i=0;i<(int)g[u].size();i++){
int v=g[u][i];
if(v==v_1||v==v_2){
continue;
}
ans_lis[++ans_len]=v;
}
}
int get_lst(int x){
return x==1?tmp_len:x-1;
}
int get_nxt(int x){
return x==tmp_len?1:x+1;
}
void find_path(int u,int S,int T){
ans_lis[++ans_len]=S;
if(S==T){
return;
}
qu_t=0;
qu[++qu_t]=u;
for(int i=head[u];i;i=nxt[i]){
int v=arrive[i];
if(in_line[v]){
continue;
}
if(deg[v]==1){
g[u].push_back(v);
pre[v]=u;
}
else{
std::reverse(qu+1,qu+1+qu_t);
find_a_line(v,u);
}
}
for(int i=1;i<=qu_t;i++){
tmp_lis[i]=(i&1)?qu[i]:-qu[i];
tmp_lis[qu_t+qu_t-i+1]=-tmp_lis[i];
}
tmp_len=0;
for(int i=1;i<=qu_t+qu_t;i++){
if(tmp_lis[i]<0){
if(g[-tmp_lis[i]].empty()){
continue;
}
}
tmp_lis[++tmp_len]=tmp_lis[i];
}
int A,B;
if(deg[S]>1){
A=S;
}
else{
A=-pre[S];
}
if(deg[T]>1){
B=T;
}
else{
B=-pre[T];
}
int pos=-1;
for(int i=1;i<=tmp_len;i++){
if(tmp_lis[i]==A){
pos=i;
break;
}
}
if(A<0){
add_a_star(-A,S,T);
}
if(tmp_lis[get_lst(pos)]==B){
for(int j=get_nxt(pos);tmp_lis[j]!=B;j=get_nxt(j)){
if(tmp_lis[j]>0){
ans_lis[++ans_len]=tmp_lis[j];
}
else{
add_a_star(-tmp_lis[j]);
}
}
}
else{
for(int j=get_lst(pos);tmp_lis[j]!=B;j=get_lst(j)){
if(tmp_lis[j]>0){
ans_lis[++ans_len]=tmp_lis[j];
}
else{
add_a_star(-tmp_lis[j]);
}
}
}
if(B<0&&A!=B){
add_a_star(-B,S,T);
}
ans_lis[++ans_len]=T;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
deg[u]++,deg[v]++;
}
Find_P::work();
for(int i=1;i<=p_len;i++){
in_line[p[i]]=1;
}
for(int i=1;i<=p_len;i++){
int u=p[i];
no_son[u]=1;
for(int j=head[u];j;j=nxt[j]){
int v=arrive[j];
if(in_line[v]){
continue;
}
no_son[u]=0;
if(deg[v]==1){
continue;
}
son_num[u]++;
if(son_num[u]>2){
puts("BRAK");
return 0;
}
if(!check(v,u)){
puts("BRAK");
return 0;
}
}
}
int tag_free=0;
for(int i=1;i<=p_len;i++){
int u=p[i];
if(no_son[u]){
tag_free=1;
}
else if(son_num[u]==2){
if(tag_free!=1){
puts("BRAK");
return 0;
}
tag_free=2;
}
}
if(tag_free==2){
puts("BRAK");
return 0;
}
int S=p[1],T;
if(no_son[p[1]]){
T=p[1];
}
else{
T=find_a_son(p[1]);
}
find_path(p[1],S,T);
for(int i=2;i<=p_len;i++){
int u=p[i];
if(no_son[u]){
S=T=u;
}
else if(!in_line[T]){
S=u;
T=find_a_leaf(u);
}
else{
S=find_a_leaf(u);
T=son_num[u]<2?u:find_a_son(u,S);
}
find_path(u,S,T);
}
if(ans_len!=n||ans_lis[ans_len]!=n){
puts("BRAK");
return 0;
}
puts("TAK");
for(int i=1;i<=n;i++){
printf("%d
",ans_lis[i]);
}
return 0;
}
