先抽象出一棵以1做为根结点的树。给定了访问序列a[1..m]。
考虑两种特殊情况：
1.访问了某个a[j]，但是存在a[i]没有访问且i < j，出现这种情况说明a[j]一定是a[i]的祖先节点，必须访问过a[j]才能访问a[i]，这种情况是不符合条件的。
2.当某个点被访问后并且这个节点被回溯之后，它的子树中仍然存在序列中的节点没被访问，那么些节点不会有机会再被访问，不符合情况。
思路：根据访问序列中节点的下标，给定所有待访问节点一个权值，代表他们的访问顺序，例如数据：
7 1 2 1 3 2 4 2 5 3 6 3 7 3 3 2 7
这组数据中，分别给3 2 7 一个权值，w[3] = 0, w[2] = 1, w[7] = 2, 其他节点的权值都是inf，dp[i]表示以节点i作为根结点的子树中最小的权值，如果某个节点i下面存在权值比它小的节点j，说明满足第一种情况，肯定是不合理的。
当处理了第一种情况，并且得到了所有dp[i]，那么现在要开始处理第二种情况。模拟深度优先遍历这棵树即可，在遍历的同时，一定是按照给定的访问序列来顺序访问，给一个全局变量f，代表当前需要访问的节点的权值，假设当前在i节点处，它的子节点是Vj，那么一定是优先访问dp[Vj] = f的节点，然后继续找，知道有节点u满足w[u] = f，说明找到了这个节点，让f++，该寻找下一个节点了，一直重复即可，注意每个节点只访问一次，当出现要访问某个被访问过的节点时，就说明符合第二种情况。其实这种方法也可以处理第一种情况，由于要预处理dp[i]，所以我在建树的同时就把第一种情况处理了。最后判断序列中是否有没被访问过得节点，有则说明是满足第二种情况的。总的复杂度是O(n*logn)
贴一组我认为很容易WA的测试数据：
6
4
1 2
2 3
3 4
3
4 3 2
7
1 2
1 3
2 4
2 5
3 6
3 7
3
3 7 2
7
1 2
1 3
2 4
2 5
3 6
3 7
3
3 2 7
4
1 2
2 3
3 4
4
4 3 2 1
7
1 2
1 3
2 4
2 5
3 6
3 7
4
2 4 3 5
9
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5
2 4 8 5 9
正确答案是:
NO
YES
NO
NO
NO
NO
AC代码：
#include <cstdio>
#include <cmath>
#include <cctype>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 100 + 5;
vector<int>G[maxn];
int vis[maxn], w[maxn], a[maxn], dp[maxn];
int n, m;
bool build_tree(int u, int par) {
if(G[u].size() == 1 && G[u][0] == par) {
dp[u] = w[u];
return true;
}
int ans = inf;
for(int i = 0; i < G[u].size(); ++i) {
int v = G[u][i];
if(v == par) continue;
if(!build_tree(v, u)) return false;
if(w[u] != inf && w[u] > dp[v]) return false;
ans = min(ans, dp[v]);
}
dp[u] = min(ans, w[u]);
return true;
}
int f;
void dfs(int u,int par) {
vis[u]++;
if(w[u] == f) f++;
if(f >= m) return;
for(int i = 0; i < G[u].size(); ++i) {
int v = G[u][i];
if(v == par) continue;
if(!vis[v] && dp[v] == f) { //未访问过f能在以v为根结点的子树中找到
dfs(v, u);
}
}
}
bool cmp(int a, int b) {
return dp[a] < dp[b];
}
bool solve(int n, int m) {
//以第一个点为根建树
bool ok = build_tree(1, -1);
if(!ok) return false;
for(int i = 1; i <= n; ++i) {
//排序,根据节点的权值确定访问顺序
sort(G[i].begin(), G[i].end(), cmp);
}
f = 0;
dfs(1, -1);
for(int i = 0; i < m; ++i) {
if(!vis[a[i]]) return false;
}
return true;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(int i = 1; i <= n+1; ++i) G[i].clear();
int u, v;
for(int i = 0; i < n-1; ++i) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; ++i) w[i] = inf;
scanf("%d", &m);
//赋予权值
for(int i = 0; i < m; ++i) {
scanf("%d", &a[i]);
w[a[i]] = i;
}
int ok = solve(n, m);
if(ok) printf("YES\n");
else printf("NO\n");
}
return 0;
}
如有不当之处欢迎指出！