给一棵树，给一个序列，问能不能按这个序列遍历这棵树，满足每条边最多经过两次。
--------------------------------------------------------------------------
因为数据小，所以直接用二维数组存储边，同时用这个数组记录边的访问次数。
因为是树，任意两个顶点间的路径只有一条，所以问题简单了很多
依次处理给定的序列，从一个顶点dfs到另一个顶点的同时检查该路径上的边是否访问超过两次了，如果超过两次则返回false
#include <set> #include <map> #include <stack> #include <queue> #include <cmath> #include <vector> #include <string> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define MAX(a,b) ((a)>=(b)?(a):(b)) #define MIN(a,b) ((a)<=(b)?(a):(b)) #define OO 0x0fffffff using namespace std; typedef long long LL; const int N = 128; int maze[N][N]; bool vis[N]; int n,m; bool dfs(int s,int e){ vis[s] = true; for(int i=1;i<=n;i++){ if(maze[s][i]&&(!vis[i])){ if(i==e||dfs(i,e)) { if(maze[s][i]>=3) return false; maze[s][i]++; maze[i][s]++; return true; } } } return false; } int main(){ int t; int a,b,c; int epos,spos; for(scanf("%d",&t);t--;){ scanf("%d",&n); memset(maze,0,sizeof(maze)); for(int i=1;i<n;i++){ scanf("%d%d",&a,&b); maze[a][b] = maze[b][a] = 1; } cin>>m; epos = 1; bool flag = true; while(m--){ spos = epos; scanf("%d",&epos); if(flag){ memset(vis,false,sizeof(vis)); flag = dfs(spos,epos); } } if(flag) puts("YES"); else puts("NO"); } return 0; }