题目链接:https://www.luogu.org/problem/CF1037D
比较容易的一道题目,直接模拟树的BFS过程就可以啦;
这里博主采用了一种神奇的方法,大家可以看一看:
用DFS搜索出每个节点的儿子个数,以及每个节点的父亲;
再直接用队列维护,模拟一下过程,对于每个点,判断当前节点的儿子个数是否符合之前所搜索出来的,
并判断其父亲是否正确,正确就又插入队列中,错误直接判断错误;
虽然慢了一点,但也不失为一个不错的方法呢!主要是灵活运用了BFS序的有关性质;
具体细节见代码:
1 #include <bits/stdc++.h> 2 #define N 200000+5 3 using namespace std; 4 int n,flag,vis[N],son[N],fa[N]; 5 vector <int> edge[N]; 6 queue <int> q; 7 void dfs(int u) 8 { 9 vis[u]=1; 10 for(int i=0;i<edge[u].size();i++) 11 { 12 int now=edge[u][i]; 13 if(!vis[now]) 14 { 15 vis[now]=1; 16 fa[now]=u; 17 son[u]++; 18 dfs(now); 19 } 20 } 21 } 22 int main() 23 { 24 scanf("%d",&n); 25 for(int i=1;i<n;i++) 26 { 27 int u,v; 28 scanf("%d%d",&u,&v); 29 edge[u].push_back(v); 30 edge[v].push_back(u); 31 } 32 dfs(1); 33 int a; 34 scanf("%d",&a); 35 if(a!=1) flag=1; 36 q.push(a); 37 memset(vis,0,sizeof(vis)); 38 vis[a]=1; 39 while(!q.empty()) 40 { 41 int now=q.front(); 42 q.pop(); 43 int cnt=son[now]; 44 for(int i=1;i<=cnt;i++) 45 { 46 scanf("%d",&a); 47 if(vis[a]) 48 { 49 flag=1; 50 continue; 51 } 52 else 53 { 54 vis[a]=1; 55 q.push(a); 56 if(fa[a]!=now) flag=1; 57 } 58 } 59 } 60 if(flag)printf("No"); 61 else printf("Yes"); 62 return 0; 63 }