Advertisement
ivnikkk

Untitled

Jul 10th, 2022
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.51 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.  
  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.     if (pr != 0) h[v] = h[pr] + 1;
  13.     gr[v].erase(find(all(gr[v]), pr));
  14.     for (int& u : gr[v]) {
  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.     int g = tin[u], ff = tin[v];
  37.     auto l = k.lower_bound(tin[u]), r = k.upper_bound(tin[v]);
  38.     vector<int> er;
  39.     for (auto it = l; it != r; it++) {
  40.         er.push_back(*it);
  41.     }
  42.     for (int& i : er) {
  43.         k.erase(i);
  44.     }
  45. }
  46. inline void up(int& u, int& v, set<int> &k) {
  47.     while (!ancestor(head[u], v)) {
  48.         func(head[u], u, k);
  49.         u = p[head[u]];
  50.     }
  51. }
  52. bool erase_try(int u, int v, set<int> &k) {
  53.     up(u, v, k);
  54.     up(v, u, k);
  55.     if (!ancestor(u, v)) swap(u, v);
  56.     func(u, v, k);
  57.     return (int)k.size() == 0;
  58. }
  59.  
  60. signed main() {
  61. #ifdef _DEBUG
  62.     freopen("input.txt", "r", stdin);
  63.     freopen("output.txt", "w", stdout);
  64. #endif
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(nullptr);
  67.     cout.tie(nullptr);
  68.     t = 0;
  69.     gr.clear(), siz.clear(), tin.clear(), tout.clear(), head.clear(), p.clear(), h.clear();
  70.     int n; cin >> n;
  71.     gr.resize(n), siz.resize(n), tin.resize(n), tout.resize(n), head.resize(n), p.resize(n), h.resize(n,0);
  72.     gr[0].push_back(0);
  73.     for (int i = 0; i < n - 1; i++) {
  74.         int u, v; cin >> u >> v;
  75.         u--, v--;
  76.         gr[u].push_back(v);
  77.         gr[v].push_back(u);
  78.     }
  79.     sizes(0, 0);
  80.     hld(0);
  81.     int q;
  82.     cin >> q;
  83.     for (int i = 0; i < q; i++) {
  84.         int x; cin >> x;
  85.         vector<int> p(x);
  86.         for (int j = 0; j < x; j++) {
  87.             cin >> p[j];
  88.             p[j]--;
  89.         }
  90.         auto cmp = [&](const int& u, const int& v) {
  91.             return h[u] < h[v];
  92.         };
  93.         sort(all(p), cmp);
  94.         reverse(all(p));
  95.         int u = p[0], v = p.back();
  96.         for (int i = 1; i < (int)p.size(); i++) {
  97.             if (!ancestor(p[i], u)) {
  98.                 v = p[i];
  99.                 break;
  100.             }
  101.         }
  102.         set<int> k;
  103.         for (int i = 0; i < (int)p.size(); i++) {
  104.             if (p[i] != u && p[i] != v) {
  105.                 k.insert(tin[p[i]]);
  106.             }
  107.         }
  108.         if (erase_try(u, v, k)) {
  109.             cout << "YES\n";
  110.         }
  111.         else {
  112.             cout << "NO\n";
  113.         }
  114.     }
  115.  
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement