SHARE
TWEET

Untitled

a guest Mar 26th, 2020 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <deque>
  5.  
  6. int depths[200000];
  7. int parents[200000];
  8. int ans[200000];
  9. std::vector<std::vector<int>> g(200000);
  10. int n, m;
  11.  
  12. void travel(int root, int parent, int depth) {
  13.   for (int child : g[root]) {
  14.     if (child != parent) {
  15.       depths[child] = depth + 1;
  16.       parents[child] = root;
  17.       travel(child, root, depth + 1);
  18.     }
  19.   }
  20. }
  21.  
  22. int main() {
  23.   std::ios_base::sync_with_stdio(false);
  24.  
  25.   std::cin >> n >> m;
  26.   for (int i = 0; i < n - 1; i++) {
  27.     int a, b;
  28.     std::cin >> a >> b;
  29.     g[a-1].push_back(b-1);
  30.     g[b-1].push_back(a-1);
  31.   }
  32.  
  33.   std::memset(depths, 0, sizeof(int) * n);
  34.   std::memset(parents, -1, sizeof(int) * n);
  35.   travel(0, -1, 0);
  36.  
  37.   for (int i = 0; i < m; i++) {
  38.     int k;
  39.     std::cin >> k;
  40.     bool possible = true;
  41.     std::memset(ans, -1, sizeof(int) * n);
  42.     for (int j = 0; j < k; j++) {
  43.       int v;
  44.       std::cin >> v;
  45.       if (!possible) {
  46.         continue;
  47.       }
  48.       int parent = parents[v-1];
  49.       //std::cout << "search for " << v << std::endl;
  50.       while(parent != -1) {
  51.         //std::cout << "parent " << parent << std::endl;
  52.         int d = depths[parent];
  53.         if (ans[d] != -1) {
  54.           if (ans[d] != parent) {
  55.             possible = false;
  56.           }
  57.           break;
  58.         }
  59.         ans[d] = parent;
  60.         parent = parents[parent];
  61.       }
  62.     }
  63.     if (possible) {
  64.       std::cout << "YES" << std::endl;
  65.     } else {
  66.       std::cout << "NO" << std::endl;
  67.     }
  68.   }
  69. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top