Advertisement
ivnikkk

Untitled

Jul 10th, 2022
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.47 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
  3. #include "bits/stdc++.h"
  4. using namespace std;
  5. #define all(d) d.begin(), d.end()
  6. #define int long long
  7. vector<vector<int>> gr;
  8. int t;
  9. vector<int> siz, tin, tout, head, p, h;
  10. void sizes(int v, int pr) {
  11.     p[v] = pr, siz[v] = 1;
  12.     gr[v].erase(find(all(gr[v]), pr));
  13.     for (int& u : gr[v]) {
  14.         h[u] = h[v] + 1;
  15.         sizes(u, v);
  16.         siz[v] += siz[u];
  17.         if (siz[u] > siz[gr[v][0]]) {
  18.             swap(u, gr[v][0]);
  19.         }
  20.     }
  21. }
  22. void hld(int v) {
  23.     tin[v] = t++;
  24.     for (int& u : gr[v]) {
  25.         if (u == gr[v][0]) head[u] = head[v];
  26.         else head[u] = u;
  27.         hld(u);
  28.     }
  29.     tout[v] = t;
  30. }
  31. bool ancestor(const int& u, const int& v) {
  32.     return tin[u] <= tin[v] && tout[u] > tin[v];
  33. }
  34. void func(int u, int v, set<int>& k) {
  35.     if (k.empty())return;
  36.     auto l = k.lower_bound(tin[u]), r = k.upper_bound(tin[v]);
  37.     vector<int> er;
  38.     for (auto it = l; it != r; it++) {
  39.         er.push_back(*it);
  40.     }
  41.     for (int& i : er) {
  42.         k.erase(i);
  43.     }
  44. }
  45. void up(int& u, int& v, set<int>& k) {
  46.     while (!ancestor(head[u], v)) {
  47.         func(head[u], u, k);
  48.         u = p[head[u]];
  49.     }
  50. }
  51. bool erase_try(int u, int v, set<int>& k) {
  52.     up(u, v, k);
  53.     up(v, u, k);
  54.     if (!ancestor(u, v)) swap(u, v);
  55.     func(u, v, k);
  56.     return (int)k.size() == 0;
  57. }
  58.  
  59. signed main() {
  60. #ifdef _DEBUG
  61.     freopen("input.txt", "r", stdin);
  62.     freopen("output.txt", "w", stdout);
  63. #endif
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(nullptr);
  66.     cout.tie(nullptr);
  67.     t = 0;
  68.     gr.clear(), siz.clear(), tin.clear(), tout.clear(), head.clear(), p.clear(), h.clear();
  69.     int n; cin >> n;
  70.     gr.resize(n), siz.resize(n), tin.resize(n), tout.resize(n), head.resize(n), p.resize(n), h.resize(n, 0);
  71.     gr[0].push_back(0);
  72.     for (int i = 0; i < n - 1; i++) {
  73.         int u, v; cin >> u >> v;
  74.         u--, v--;
  75.         gr[u].push_back(v);
  76.         gr[v].push_back(u);
  77.     }
  78.     sizes(0, 0);
  79.     hld(0);
  80.     int q;
  81.     cin >> q;
  82.     for (int i = 0; i < q; i++) {
  83.         int x; cin >> x;
  84.         vector<int> p(x);
  85.         for (int j = 0; j < x; j++) {
  86.             cin >> p[j];
  87.             p[j]--;
  88.         }
  89.         auto cmp = [&](const int& u, const int& v) {
  90.             return h[u] < h[v];
  91.         };
  92.         sort(all(p), cmp);
  93.         reverse(all(p));
  94.         int u = p[0], v = p.back();
  95.         for (int i = 1; i < (int)p.size(); i++) {
  96.             if (!ancestor(p[i], u)) {
  97.                 v = p[i];
  98.                 break;
  99.             }
  100.         }
  101.         set<int> k;
  102.         for (int i = 0; i < (int)p.size(); i++) {
  103.             if (p[i] != u && p[i] != v) {
  104.                 k.insert(tin[p[i]]);
  105.             }
  106.         }
  107.         if (erase_try(u, v, k)) {
  108.             cout << "YES\n";
  109.         }
  110.         else {
  111.             cout << "NO\n";
  112.         }
  113.     }
  114.  
  115. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement