D. Ant on the Tree
time limit per test
memory limit per test
input
output
Connected undirected graph without cycles is called a tree. Trees is a class of graphs which is interesting not only for people, but for ants too.
An ant stands at the root of some tree. He sees that there are n vertexes in the tree, and they are connected by n - 1
The ant wants to visit every vertex in the tree and return to the root, passing every edge twice. In addition, he wants to visit the leaves in a specific order. You are to find some possible route of the ant.
Input
The first line contains integer n (3 ≤ n ≤ 300) — amount of vertexes in the tree. Next n - 1 lines describe edges. Each edge is described with two integers — indexes of vertexes which it connects. Each edge can be passed in any direction. Vertexes are numbered starting from 1. The root of the tree has number 1. The last line contains k integers, where k
Output
If the required route doesn't exist, output -1. Otherwise, output 2n - 1
Examples
input
3
1 2
2 3
3
output
1 2 3 2 1
input
6
1 2
1 3
2 4
4 5
4 6
5 6 3
output
1 2 4 5 4 6 4 2 1 3 1
input
6
1 2
1 3
2 4
4 5
4 6
5 3 6
output
-1
通过深搜求出树上每个节点孩子的数目d[]和父节点pre[].叶子节点按顺序存在k数组中,先保存从根节点1到k[0]的路径，再遍历k[0]的父节点，遇到1个父节点d[]--,直到减完之后孩子数目大于1的第一个节点e, 在记录k[0]到e的路径，判断e是否为k[1]的父节点(通过pre[]数组)若没有结束程序输出-1，若有记录e到k[1]的路径，以此类推
#include <bits/stdc++.h>
#define maxn 100005
#define MOD 1000000007
using namespace std;
typedef long long ll;
int route[1005], d[305], k[305], pre[305], p[305];
vector<int> v[305];
int cnt = 0;
void dfs(int i, int f){
for(int j = 0; j < v[i].size(); j++){
if(v[i][j] != f){
pre[v[i][j]] = i;
dfs(v[i][j], i);
}
}
}
int solve(int k1, int k2, int t){\\判断k2是否为k1父节点，并且记录路径
int j = 0, sign = 0;
p[j++] = k1;
while(pre[k1]){
k1 = pre[k1];
p[j++] = k1;
if(k1 == k2){
sign = 1;
break;
}
}
if(sign == 0)
return 0;
if(t == 1){
for(int i = 0; i < j; i++){
route[cnt++] = p[i];
}
}
else{
for(int i = j-1; i >= 0; i--){
route[cnt++] = p[i];
}
}
return 1;
}
int main(){
// freopen("in.txt", "r", stdin);
int n, a, b;
scanf("%d", &n);
memset(d, -1, sizeof(d));
for(int i = 0; i < n-1; i++){
scanf("%d%d", &a, &b);
d[a]++;
d[b]++;
v[a].push_back(b);
v[b].push_back(a);
}
d[1]++;
dfs(1, -1);
int e = 0;
while(1){
scanf("%d", k+e);
e++;
if(getchar() == '\n')
break;
}
solve(k[0], 1, 2);
for(int i = 1; i < e; i++){
int m = k[i-1];
while(1){
m = pre[m];
d[m]--;
if(d[m] > 0)
break;
}
solve(k[i-1], m, 1);
if(solve(k[i], m, 2) == 0){
puts("-1");
return 0;
}
}
solve(k[e-1], 1, 1);
printf("%d", route[0]);
for(int i = 1; i < cnt; i++){
if(route[i] != route[i-1]){
printf(" %d", route[i]);
}
}
puts("");
return 0;
}