题目
给定一棵树，N个节点，N - 1条边。给定m个节点，能否找出一种遍历方法，使得首次到达节点ai的时间小于首次到达节点aj的时间（i < j)。且经过的路径上的每条边都最多走两遍
分析
我的想法：
深度优先搜索的策略，在进入某个节点A时，以该节点A为根的子树中的所有节点构成一个集合，该集合内的点将在 m个点集合中连在一块，
而在节点A为根的子树之外的点不能混在其中。
在实现的时候，定义全局数组 gBlocked[]，gBlocked[i] 表示节点i将不能再访问（需要判断并标记）， gVisited[i] 表示节点i在当前已经被访问过（
在之前访问其他节点的路径上被经过）。
从头到尾遍历m个点，对于点Mi：
1）如果该节点在之前被访问过，则失败！
2）找出从Mi向上到达根的路径 path_new，并将路径上的点都标记为 访问过；
在从节点Mi出发寻找Mi到根节点的路径的时候，如果中间某个节点的状态为“不能在访问”，则失败！
3）然后，和前一个点Mi-1 形成的路径 path_old 进行比较，找出 Mi 和 Mi-1的最低的公共祖先节点 P. 然后将 从P到Mi-1的路径中，P之后的那个节点t标记
为 “不能再访问” 状态（gBlocked[t] = true)，因为此时已经从节点t的子树中出来了。
遍历完所有m个节点之后，返回成功！
参考网上的想法：
1.预处理，确定每个节点出发可以到达的所有节点。（通过父节点可以到达子节点到达的所有节点进行递归）
2.从根节点开始按照顺序访问m个点，在访问点 Mi 的时候，若当前点为P， 则P的子节点中寻找能够到达 Mi
的节点 Q，然后递归到Q，并将Q标记为“访问过”， 从P找不到可以访问到Mi的子节点，则回溯到P的父节点T， 从T
再递归
直到访问完所有的节点，或者中间的某个节点递归到根节点仍然无法访问
实现
解法1
/*
深度优先搜索的策略，在进入某个节点A时，以该节点A为根的子树中的所有节点构成一个集合，该集合内的点将在 m个点集合中连在一块，
而在节点A为根的子树之外的点不能混在其中。
在实现的时候，定义全局数组 gBlocked[]，gBlocked[i] 表示节点i将不能再访问（需要判断并标记）， gVisited[i] 表示节点i在当前已经被访问过（
在之前访问其他节点的路径上被经过）。
从头到尾遍历m个点，对于点Mi：
1）如果该节点在之前被访问过，则失败！
2）找出从Mi向上到达根的路径 path_new，并将路径上的点都标记为 访问过；
在从节点Mi出发寻找Mi到根节点的路径的时候，如果中间某个节点的状态为“不能在访问”，则失败！
3）然后，和前一个点Mi-1 形成的路径 path_old 进行比较，找出 Mi 和 Mi-1的最低的公共祖先节点 P. 然后将 从P到Mi-1的路径中，P之后的那个节点t标记
为 “不能再访问” 状态（gBlocked[t] = true)，因为此时已经从节点t的子树中出来了。
遍历完所有m个节点之后，返回成功！
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<deque>
using namespace std;
#define N 120
struct Edge{
int to;
int next;
Edge(int t = -1, int n = -1) :to(t), next(n){};
};
Edge gEdges[N];
int gEdgeIndex;
int gHead[N];
bool gVisited[N];
int gPre[N];
int gTravelSeq[N];
bool gBlocked[N];
void InsertEdge(int u, int v){
int e = gEdgeIndex++;
gEdges[e].to = v;
gEdges[e].next = gHead[u];
gHead[u] = e;
e = gEdgeIndex++;
gEdges[e].to = u;
gEdges[e].next = gHead[v];
gHead[v] = e;
}
//Dfs确定树的结构，因为一开始给的点对不一定是 父--子 ，所以需要遍历图来进行确定树的父子关系
void Dfs(int u){
gVisited[u] = true;
for (int e = gHead[u]; e != -1; e = gEdges[e].next){
int v = gEdges[e].to;
if (!gVisited[v]){
gPre[v] = u;
Dfs(v);
}
}
}
//寻找从节点u向上到根节点的路径
bool Path(int u, deque<int>& path){
path.clear();
while (u != -1){
if (gBlocked[u]){
return false;
}
gVisited[u] = true;
path.push_back(u);
u = gPre[u];
}
return true;
}
//判断是否可以按照顺序遍历这m个节点，n为节点的数目
bool CanTravel(int m, int n){
if (m <= 0)
return false;
if (gTravelSeq[0] > n)
return false;
memset(gVisited, false, sizeof(gVisited));
deque<int> last_path; //保存路径
bool can_path = Path(gTravelSeq[0], last_path);
deque<int> path;
for (int i = 1; i < m; i++){
int u = gTravelSeq[i];
if (u > n || gVisited[u]) //节点u在访问之前的节点过程中被访问该，返回失败
return false;
can_path = Path(gTravelSeq[i], path);
if (!can_path) //寻找从节点u到根节点的路径时，遇到了 “不能再访问”的节点，返回失败
return false;
int k1 = last_path.size() - 1;
int k2 = path.size() - 1;
//寻找最近公共祖先
while (k1 >= 0 && k2 >= 0 && last_path[k1] == path[k2])
{
--k1;
--k2;
}
if (k1 >= 0) //最近公共祖先到 gTravelSeq[i-1]的的下一个点，标记为不能再访问
gBlocked[last_path[k1]] = true;
last_path = path;
}
return true;
}
void Init(){
memset(gVisited, false, sizeof(gVisited));
memset(gPre, -1, sizeof(gPre));
memset(gEdges, -1, sizeof(gEdges));
memset(gHead, -1, sizeof(gHead));
memset(gBlocked, false, sizeof(gBlocked));
gEdgeIndex = 0;
}
int main2(){
int T, n, m, u, v;
scanf("%d", &T);
while (T--){
Init();
scanf("%d", &n);
for (int i = 0; i < n - 1; i++){
scanf("%d %d", &u, &v);
InsertEdge(u, v);
}
Dfs(1);
scanf("%d", &m);
for (int i = 0; i < m; i++){
scanf("%d", &(gTravelSeq[i]));
}
bool ret = CanTravel(m, n);
if (ret)
printf("YES
");
else
printf("NO
");
}
return 0;
}
解法2
/*
参考网上的做法：
1.预处理，确定每个节点出发可以到达的所有节点。（通过父节点可以到达子节点到达的所有节点进行递归）
2.从根节点开始按照顺序访问m个点，在访问点 Mi 的时候，若当前点为P， 则P的子节点中寻找能够到达 Mi
的节点 Q，然后递归到Q，并将Q标记为“访问过”， 从P找不到可以访问到Mi的子节点，则回溯到P的父节点T， 从T
再递归
直到访问完所有的节点，或者中间的某个节点递归到根节点仍然无法访问
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<deque>
#include<bitset>
using namespace std;
#define N 120
struct Edge{
int to;
int next;
Edge(int t = -1, int n = -1) :to(t), next(n){};
};
Edge gEdges[N];
int gEdgeIndex;
int gHead[N];
bool gVisited[N];
int gPre[N];
int gTravelSeq[N];
bitset<N> gCanReach[N]; //判断节点是否可以到达其他节点，用bitset可以方便的进行位操作
void InsertEdge(int u, int v){
int e = gEdgeIndex++;
gEdges[e].to = v;
gEdges[e].next = gHead[u];
gHead[u] = e;
e = gEdgeIndex++;
gEdges[e].to = u;
gEdges[e].next = gHead[v];
gHead[v] = e;
}
//确定从u可以到达的所有节点
void CanReach(int u){
gCanReach[u][u] = 1;
gVisited[u] = true;
for (int e = gHead[u]; e != -1; e = gEdges[e].next){
int v = gEdges[e].to;
if (!gVisited[v]){ //若为true，则说明v为u的父节点
gPre[v] = u;
CanReach(v);
gCanReach[u] |= gCanReach[v];
}
}
}
//当前节点为u，需要 按照顺序遍历的索引为 index， m为需要访问的节点数目
bool CanTravel(int u, int index, int m){
if (index == m) //所有节点都访问过了
return true;
if (u == -1) //最后无法继续向下访问
return false;
gVisited[u] = true;
if (u == gTravelSeq[index]){ //访问到一个节点，从当前节点开始继续下一个
return CanTravel(u, index + 1, m);
}
for (int e = gHead[u]; e != -1; e = gEdges[e].next){
int v = gEdges[e].to;
//从当前节点的子节点中查找之前没有经过的，且能够到达目标节点的
if (!gVisited[v] && gCanReach[v][gTravelSeq[index]]){
return CanTravel(v, index, m);
}
}
//回溯到上一层节点
return CanTravel(gPre[u], index, m);
}
void Init(){
memset(gVisited, false, sizeof(gVisited));
memset(gEdges, -1, sizeof(gEdges));
memset(gHead, -1, sizeof(gHead));
memset(gPre, -1, sizeof(gPre));
for (int i = 0; i < N; i++){
gCanReach[i].reset(0);
}
gEdgeIndex = 0;
}
int main(){
int T, n, m, u, v;
scanf("%d", &T);
while (T--){
Init();
scanf("%d", &n);
for (int i = 0; i < n - 1; i++){
scanf("%d %d", &u, &v);
InsertEdge(u, v);
}
CanReach(1);
scanf("%d", &m);
for (int i = 0; i < m; i++){
scanf("%d", &(gTravelSeq[i]));
}
memset(gVisited, false, sizeof(gVisited));
bool ret = CanTravel(1, 0, m);
if (ret)
printf("YES
");
else
printf("NO
");
}
return 0;
}