给一颗树,1为根,要求遍历树上所有点,给出叶子结点的访问顺序,限制每条边至多访问两次。
首先这是一棵树,那么两点之间的路线是确定的,所以我第一遍dfs预处理出从根节点到每个叶子的路径保存,以便后面输出。
那么就按照题目要求输出叶子结点的顺序依次输出,然后从一个叶子到下一个叶子的时候,从他们的最近公共祖先转折,所以我还预处理了相邻两个叶子结点的LCA。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#pragma comment(linker, "/STACK:16777216")
#define eps 1e-6
#define ll long long
using namespace std;
const int maxn=310;
struct node
{
int v,id,w;//id为边号或询问号
node* next;
}ed[maxn<<2],*head[maxn],*q[maxn];
struct qnode
{
int u,v,ans;//存询问结点,ans最近公共祖先
} qu[maxn];
int fa[maxn],vis[maxn],cnt;
void init(int n)
{
cnt=0;
memset(vis,0,sizeof vis);
memset(head,0,sizeof head);
memset(q,0,sizeof q);
for(int i=0;i<=n;i++)
fa[i]=i;
}
int getfa(int x)
{
if(fa[x]==x) return x;
return fa[x]=getfa(fa[x]);
}
void LCA(int u)
{
fa[u]=u,vis[u]=1;
for(node *p=q[u];p!=NULL;p=p->next)
{
if(vis[p->v])
{
int id=p->id;
qu[id].ans=getfa(p->v);
}
}
for(node *p=head[u];p!=NULL;p=p->next)
{
if(!vis[p->v])
{
LCA(p->v);
fa[p->v]=u;
}
}
}
void adde(node *e[],int u,int v,int w,int id)//建边e传头节点数组。为询问边的或树边的。
{
ed[cnt].v=v;
ed[cnt].w=w;
ed[cnt].id=id;
ed[cnt].next=e[u];
e[u]=&ed[cnt++];
}
inline int ReadInt()
{
char ch = getchar();
if (ch==EOF) return -1;
int data = 0;
while (ch < '0' || ch > '9')
{
ch = getchar();
if (ch==EOF) return -1;
}
do
{
data = data*10 + ch-'0';
ch = getchar();
} while (ch >= '0' && ch <= '9');
return data;
}
int f[maxn],leaf[maxn],ans[610],flag;
void dfs(int s)
{
for(node *p=head[s];p!=NULL;p=p->next)
{
if(!vis[p->v])
{
vis[p->v]=1;
f[p->v]=s;
dfs(p->v);
}
}
}
void output(int s,int t)//r->leaf
{
if(f[t]!=s)
output(s,f[t]);
ans[cnt++]=t;
flag++;
}
void output1(int s,int t)//leaf->r
{
do
{
flag++;
ans[cnt++]=f[s];
s=f[s];
}while(s!=t);
}
int main()
{
int n,a,b,i,k;
scanf("%d",&n);
init(n);
for(i=0;i<n-1;i++)
{
scanf("%d%d",&a,&b);
adde(head,a,b,1,i);
adde(head,b,a,1,i);
}
k=0;
while((leaf[k]=ReadInt())!=-1) k++;
for(i=1;i<k;i++)
{
adde(q,leaf[i],leaf[i-1],1,i);
adde(q,leaf[i-1],leaf[i],1,i);
}
LCA(1);
memset(vis,0,sizeof vis);
memset(f,-1,sizeof f);
vis[1]=1;
dfs(1);
cnt=0;flag=1;
ans[cnt++]=1;
output(1,leaf[0]);
if(flag<=n+n-1)
for(i=1;i<k;i++)
{
output1(leaf[i-1],qu[i].ans);
if(flag>n+n-1) break;
output(qu[i].ans,leaf[i]);
if(flag>n+n-1) break;
}
if(flag<=n+n-1) output1(leaf[k-1],1);
if(flag<=n+n-1)
{
printf("1");
for(i=1;i<cnt;i++)
printf(" %d",ans[i]);
puts("");
}
else printf("-1\n");
return 0;
}