Advertisement
Aqib12

KPATH_codechef

Jul 9th, 2021
1,133
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.57 KB | None | 0 0
  1. #include <algorithm>
  2. #include <array>
  3. #include <bitset>
  4. #include <cassert>
  5. #include <chrono>
  6. #include <cmath>
  7. #include <cstring>
  8. #include <functional>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <map>
  12. #include <numeric>
  13. #include <queue>
  14. #include <random>
  15. #include <set>
  16. #include <vector>
  17. using namespace std;
  18.  
  19. using ll = long long;
  20. using ld = long double;
  21.  
  22. template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
  23. template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
  24.  
  25. void dbg_out() { cerr << endl; }
  26. template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
  27. #ifdef AQIB_DEBUG
  28. #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
  29. #else
  30. #define dbg(...)
  31. #endif
  32.  
  33. template<typename T_vector>
  34. void output_vector(const T_vector &v, int add_val = 0) {
  35.   for (int i = 0; i < int(v.size()); i++) cout << v[i] + add_val << (i != int(v.size()) - 1 ? ' ' : '\n');
  36. }
  37.  
  38. // usage:
  39. //   auto fun = [&](int i, int j) { return min(i, j); };
  40. //   SparseTable<int, decltype(fun)> st(a, fun);
  41. // or:
  42. //   SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
  43. template <typename T, class F = function<T(const T&, const T&)>>
  44. class SparseTable {
  45.  public:
  46.   int n;
  47.   vector<vector<T>> mat;
  48.   F func;
  49.  
  50.   SparseTable(const vector<T>& a, const F& f) : func(f) {
  51.     n = static_cast<int>(a.size());
  52.     int max_log = 32 - __builtin_clz(n);
  53.     mat.resize(max_log);
  54.     mat[0] = a;
  55.     for (int j = 1; j < max_log; j++) {
  56.       mat[j].resize(n - (1 << j) + 1);
  57.       for (int i = 0; i <= n - (1 << j); i++) {
  58.         mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
  59.       }
  60.     }
  61.   }
  62.  
  63.   T get(int from, int to) const {
  64.     assert(0 <= from && from <= to && to <= n - 1);
  65.     int lg = 32 - __builtin_clz(to - from + 1) - 1;
  66.     return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  67.   }
  68. };
  69.  
  70. vector<vector<int>> adj;
  71. vector<bool> vis;
  72. vector<int> depth;
  73. vector<int> node_track;
  74. vector<int> last;
  75. vector<int> tree_depth;
  76.  
  77. int tour_index;
  78.  
  79. void visit(int node, int d) {
  80.   node_track[tour_index] = node;
  81.   depth[tour_index] = d;
  82.   last[node] = tour_index;
  83.   tour_index += 1;
  84. }
  85.  
  86. void dfs(int cur, int par, int d) {
  87.   tree_depth[cur] = d;
  88.   visit(cur, d);
  89.   for (int node : adj[cur]) {
  90.     if (node == par) continue;
  91.     dfs(node, cur, d + 1);
  92.     visit(cur, d);
  93.   }
  94. }
  95.  
  96. void solve() {
  97.   int n;
  98.   cin >> n;
  99.  
  100.   adj = vector<vector<int>>(n);
  101.   vis = vector<bool>(n);
  102.   depth = vector<int>(2 * n - 1);
  103.   node_track = vector<int>(2 * n - 1);
  104.   last = vector<int>(n);
  105.   tree_depth = vector<int>(n);
  106.  
  107.   vector<int> a(n);
  108.   for (int i = 0; i < n - 1; i++) {
  109.     int u, v;
  110.     cin >> u >> v;
  111.     --u, --v;
  112.     adj[u].push_back(v);
  113.     adj[v].push_back(u);
  114.   }
  115.  
  116.   tour_index = 0;
  117.   dfs(0, -1, 0);
  118.  
  119.   SparseTable<int> sp(depth, [](int i, int j) {return min(i, j);});
  120.  
  121.   auto get_lca = [&](int a, int b) {
  122.     int l = min(last[a], last[b]);
  123.     int r = max(last[a], last[b]);
  124.     return node_track[sp.get(l, r)];
  125.   };
  126.  
  127.   int q;
  128.   cin >> q;
  129.   while (q--) {
  130.     int k;
  131.     cin >> k;
  132.     vector<int> check(k);
  133.     for (int &i : check) {
  134.       cin >> i;
  135.       --i;
  136.     }
  137.  
  138.     if (k <= 2) {
  139.       cout << "YES" << '\n';
  140.       continue;
  141.     }
  142.  
  143.     sort(check.rbegin(), check.rend(),
  144.          [&](int a, int b) { return tree_depth[a] < tree_depth[b]; });
  145.  
  146.  
  147.     int present = check[0];
  148.     int idx = 0;
  149.     for (int i = 1; i < k; i++) {
  150.       present = get_lca(present, check[i]);
  151.       if (present == check[i]) {
  152.         continue;
  153.       }
  154.       idx = i + 1;
  155.       break;
  156.     }
  157.  
  158.     bool ans = true;
  159.  
  160.     int left = check[idx - 2], right = check[idx - 1];
  161.     for (int i = idx; i < k; i++) {
  162.       int with_present = get_lca(present, check[i]);
  163.       int with_left = get_lca(check[i], left);
  164.       int with_right = get_lca(check[i], right);
  165.  
  166.       ans &= with_present == present;
  167.       ans &= with_left == present or with_left == check[i];
  168.       ans &= with_right == present or with_right == check[i];
  169.     }
  170.  
  171.     cout << (ans ? "YES" : "NO") << '\n';
  172.   }
  173. }
  174.  
  175. int main() {
  176.   ios_base::sync_with_stdio(false);
  177. #ifndef AQIB_DEBUG
  178.   cin.tie(nullptr);
  179. #endif
  180.  
  181.   int t;
  182.   cin >> t;
  183.  
  184.   while (t--) solve();
  185.   return 0;
  186. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement