问题：详见http://hihocoder.com/problemset/problem/1041
有n个城市，城市编号为1-n，城市间有n-1条路（所以，城市路网是一棵树）。给定一个序列S，要求判断是否存在一条路径，使得
- 从城市 1 开始出发，每条路都需通过2次，最后回到1
- 对于S中的城市，访问的顺序要从前到后。因为每条路可以走两次，所以这里要求的是第一次经过的顺序
思路：DFS
1. 预处理：找出所有结点的可达结点。
通过这个，我们就可以快速判断某个结点是否在某个子树中。比如下一个的访问目标为3，当前的位置是1，那么通过判断3是否在1的某个子树中，可以直接决定下一步应该选择哪个结点。
2. 从结点1开始深搜。直到按序访问到序列S中的每个点
#include <iostream>
#include <bitset>
#include <string> using namespace std;
#define maxCity 100
bitset<maxCity> roads[maxCity];//标识两个城市之间有路
bitset<maxCity> reach[maxCity];//标识一个点的子节点，也就是到哪些点是可达的 void setReach(int curr, int father, int cityCnt){
reach[curr][curr] = ;//自己到自己是可达的
for (int son = ; son <= cityCnt; son++){
if (father == son)
continue;
if (roads[curr][son]){//如果father 和 son 之间是有路的
setReach(son, curr, cityCnt);//计算son的可达点
reach[curr] |= reach[son];//通过 或 操作，把son的可达点加入到curr的可达集合中
}
}
}
//当前访问到的城市 currID
//下一个应该访问在要求序列中的第 rIndex 个城市
//要求的序列包含 rCnt 个城市
int rIndex = ;
bool flag = false;//是否找到满足条件的路径
void dfs(int currID, int father, int rCnt, int* rCity, int cityCnt){
if (currID == rCity[rIndex])//当前要访问的正好是序列中的下一个城市
++rIndex;
if (rIndex == rCnt){//序列的要求已经满足
flag = true;
return;
}
while (rIndex < rCnt){//判断从当前点继续是否能走完整个要求的序列
int i = ;
for (; i <= cityCnt; i++){
if (i == currID || i == father)
continue;
//遍历currID的所有子节点，每个节点代表了一棵子树
//roads[currID][i] 不为0， 表明currID和i有路
//reach[i][rCity[rIndex]] 不为0，表明从i可以直到要求序列的下一个城市
//同时满足条件，也就是说currID的下一个可以访问i，然后通过 i 走到下一个要求的城市
if (roads[currID][i] && reach[i][rCity[rIndex]]){
roads[currID][i] = ;
dfs(i, currID, rCnt, rCity, cityCnt);//访问 i 这棵子树
break;//每个节点只能属于一棵子树，所以其它的就不用再判断。已经知道下一个要求的节点在 i 的子树中，所以不需要再去判断其它节点的子树
}
}
if (i > cityCnt)//没有在currID中的任何一个子树中找到下一个要求的结点
break;
}
}
int main(){
int cnt, cityCnt, rCnt, *rCity;
cin >> cnt; while (cnt-- > ){
flag = false;
cin >> cityCnt;
rIndex = ;
//初始化，城市间都没有路，都没有子节点
for (int i = ; i <= cityCnt; i++){
roads[i].reset();
reach[i].reset();
}
for (int i = ; i < cityCnt - ; i++){
int a, b;
//a, b间有路
cin >> a >> b;
roads[a][b] = ;
roads[b][a] = ;
}
cin >> rCnt;
rCity = new int[rCnt];
for (int i = ; i < rCnt; i++)
cin >> rCity[i];
setReach(, -, cityCnt);
dfs(, -, rCnt, rCity, cityCnt);
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return ;
}
注：
1. bitset 需要#include <bitset>
bitset<maxCity> roads[maxCity] 声明了一个数组，数组的元素类型为bitset<maxCity>，每一个数用maxCity位的二进制来表示
2. 在计算每个点可达的集合，以及寻找路径的时候都有一个判断条件：判断当前点的son是否和父节点father一样
如果不进行这个判断，假设树的结构为 1-2，也就是只有两个城市1、2，它们中间有一条路。以setReach为例，递归的过程如下：
setReach(1, -1)->(因为1可以到达2)setReach(2, 1)->（从城市1开始判断，2可以到达1）setReach(1, 2)->setReach(2,1)...死循环
这里只需要考虑当前点的父结点，而不用继续向上考虑，是因为当前点和父结点的上层并不会有路径。