fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  3. #define ll long long
  4. #define ld long double
  5. #define pb push_back
  6. using namespace std;
  7. vector<vector<int>>v;
  8. vector<int>d;
  9. set<int>s;
  10. int mx=0;
  11. void depth(int node,int p){
  12.     if(p >= 0) d[node] = d[p] + 1;
  13.     for(int child: v[node]){
  14.         if(child == p) continue;
  15.         depth(child,node);
  16.     }
  17. }
  18. bool o=0;
  19. bool vis[(int)2e5+5];
  20. void dfs(int node,int cnt)
  21. {
  22.     vis[node]=1;
  23.     if(v[node].size()<=1)
  24.     {
  25.             if(cnt==s.size())
  26.                 o=1;
  27.     }
  28.     for(auto child:v[node])
  29.     {
  30.         if(!vis[child])
  31.         {
  32.             if(s.find(child)!=s.end())
  33.             dfs(child,cnt+1);
  34.         else dfs(child,cnt);
  35.         }
  36.     }
  37. }
  38. int main()
  39. {
  40. fast
  41. int n;
  42. cin>>n;
  43. int x,y;
  44. v.resize(n+2);
  45. d.resize(n+2);
  46. for(int i=0;i<n-1;i++)
  47. {
  48.     cin>>x>>y;
  49.     v[x].pb(y);
  50.     v[y].pb(x);
  51. }
  52. depth(1,-1);
  53. int q;
  54. cin>>q;
  55. while(q--)
  56. {
  57.     int k,f;
  58.     cin>>k;
  59.     mx=0;
  60.     s.clear();
  61.     o=0;
  62.     for(int i=0;i<k;i++)
  63.     {
  64.         cin>>f;
  65.         s.insert(f);
  66.         if(d[f]>d[mx])
  67.         mx=f;
  68.     }
  69.     for(int i=1;i<=n;i++) vis[i]=0;
  70.     dfs(mx,1);
  71.     cout<<(o?"YES\n":"NO\n");
  72. }
  73. return 0;
  74. }
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/npt1hj
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!