小Hi和小Ho准备国庆期间去A国旅游。A国的城际交通比较有特色：它共有n座城市(编号1-n)；城市之间恰好有n-1条公路相连，形成一个树形公路网。小Hi计划从A国首都(1号城市)出发，自驾遍历所有城市，并且经过每一条公路恰好两次——来回各一次——这样公路两旁的景色都不会错过。
令小Hi苦恼的是他的小伙伴小Ho希望能以某种特定的顺序游历其中m个城市。例如按3-2-5的顺序游历这3座城市。(具体来讲是要求：第一次到达3号城市比第一次到达2号城市早，并且第一次到达2号城市比第一次到达5号城市早)。
小Hi想知道是否有一种自驾顺序满足小Ho的要求。
Input
输入第一行是一个整数T(1<=T<=20)，代表测试数据的数量。
每组数据第一行是一个整数n(1 <= n <= 100)，代表城市数目。
之后n-1行每行两个整数a和b (1 <= a, b <= n)，表示ab之间有公路相连。
之后一行包含一个整数m (1 <= m <= n)
最后一行包含m个整数，表示小Ho希望的游历顺序。
Output
YES或者NO，表示是否有一种自驾顺序满足小Ho的要求。
Sample Input
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
Sample Output
YES
NO
实际也算不上是DP，感觉就是搜索。自己的思路，1A，开心。
思路：你如果访问了一个节点node，你必须也把子树中需要访问的给访问了，不然你的fa_node到node这条路将走超过两遍。
要求：node的几个子树中需要访问的点肯定要在顺序的相连位置。
其中：sa是每个点的顺序，son[node]表示node根下需要访问的点的顺序
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<memory>
#include<cstring>
using namespace std;
int sa[],son[][];//sa是每个点的顺序，son[node]表示node根下需要访问的点的顺序
int Laxt[],Next[],To[],cnt,vis[]; void _add(int u,int v)//加边
{
Next[++cnt]=Laxt[u];
Laxt[u]=cnt;
To[cnt]=v;
} bool _check(int u)//检查不包括u节点的u的子树中需要访问的点的顺序是否连续
{
sort(son[u]+,son[u]++son[u][]);//排序后方便检查
for(int i=;i<=son[u][];i++)
if(son[u][i]!=son[u][i-]+) return false;
return true;
} bool _dfs(int u)
{
vis[u]=;
for(int i=Laxt[u];i;i=Next[i]){
int v=To[i];
if(vis[v]) continue;
if(!_dfs(v)) return false;
for(int j=;j<=son[v][];j++) son[u][++son[u][]]=son[v][j];//加子树
}
if(!_check(u))return false;//检查子树
if(sa[u]&&son[u][]>&&sa[u]+!=son[u][]) return false;//根是不是第一个
if(sa[u]) son[u][++son[u][]]=sa[u];//加根
return true;
} int main()
{
int T,i,j,n,m,u,v;
scanf("%d",&T); while(T--){
memset(sa,,sizeof(sa));
memset(Laxt,,sizeof(Laxt));
memset(son,,sizeof(son));
memset(vis,,sizeof(vis));
cnt=; scanf("%d",&n);
for(i=;i<n;i++) {
scanf("%d%d",&u,&v);
_add(u,v);_add(v,u);
} scanf("%d",&m);
for(i=;i<=m;i++){
scanf("%d",&j);sa[j]=i;
} if(_dfs()) printf("YES\n");
else printf("NO\n"); }
return ;
}