Guest User

Untitled

a guest
Mar 27th, 2020
336
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.33 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define DEBUG true
  6. #define ll int
  7. #define tki(x) int x;scanf("%d",&x);
  8. #define tkll(x) ll x;scanf("%ll",&x);
  9. #define vll vector<ll>
  10. #define vii vector<int>
  11. #define PB push_back
  12. #define EB emplace_back
  13. #define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  14. #define forll(i,j,k) for(ll i=j;i<k;i++)
  15. #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
  16. #define all(x) (x).begin(), (x).end()
  17. #define endl "\n"
  18.  
  19. class Node{
  20.     public:
  21.     int height;
  22.     int parent;
  23.     vector<int> child;
  24. };
  25. // vector<Node *> T;/
  26. void dfs(vector<Node *> &T,ll a){
  27.     for(auto x : T[a]->child){
  28.         T[x]->height = (T[a]->height) + 1;
  29.         dfs(T,x);
  30.     }
  31. }
  32. int main(){
  33.     FASTIO
  34.     tki(N);tki(M);
  35.     int *height = new int[N];
  36.     int *parent = new int[N];
  37.     {
  38.        vector<Node *> T(N);
  39.         rep(i,0,N){T[i] = new Node;}  
  40.         T[0]->height = 1;
  41.         T[0]->parent = 0;
  42.         rep(i,0,N-1){
  43.             tki(a);tki(b);
  44.             (T[min(a-1,b-1)]->child).EB(max(a-1,b-1));
  45.             T[max(a-1,b-1)]->parent = min(a-1,b-1);
  46.         }
  47.         dfs(T,0);
  48.         forll(i,0,N){height[i] = T[i]->height;parent[i] = T[i]->parent;}
  49.     }
  50.  
  51.     // delete &T;
  52.     int K;
  53.     int maxi = 0;
  54.     int lastNode = 0;
  55.     vector<int> v;
  56.     vector<int> path;
  57.     forll(i,0,M){
  58.         scanf("%d",&K);
  59.         v.resize(K);
  60.         for(int i=0;i<K;i++){
  61.             scanf("%d",&v[i]);
  62.             v[i]--;
  63.         }
  64.         if(K >= 2){
  65.             maxi = 0;
  66.             lastNode = 0;
  67.             forll(j,0,K){
  68.                 if(height[v[j]] > maxi){maxi= height[v[j]];lastNode = v[j];}
  69.             }
  70.             path.resize(maxi);
  71.             path[maxi-1] = lastNode;
  72.  
  73.             for(ll j = maxi-2;j>=0;j--){
  74.                 path[j] = parent[path[j+1]];
  75.             }
  76.             bool f = true;
  77.             forll(j,0,K){
  78.                 if(height[v[j]] >= 2){
  79.                     if(parent[v[j]] != path[height[v[j]] - 2]){f=false;break;}
  80.                 }
  81.             }
  82.             if(f){printf("YES\n");}
  83.             else{
  84.                 printf("NO\n");
  85.             }
  86.         }
  87.         else{
  88.             printf("YES\n");
  89.         }
  90.     }
  91. }
Add Comment
Please, Sign In to add comment