Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <array>
- #include <bitset>
- #include <cassert>
- #include <chrono>
- #include <cmath>
- #include <cstring>
- #include <functional>
- #include <iomanip>
- #include <iostream>
- #include <map>
- #include <numeric>
- #include <queue>
- #include <random>
- #include <set>
- #include <vector>
- using namespace std;
- using ll = long long;
- using ld = long double;
- template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
- 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 << '}'; }
- void dbg_out() { cerr << endl; }
- template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
- #ifdef AQIB_DEBUG
- #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
- #else
- #define dbg(...)
- #endif
- template<typename T_vector>
- void output_vector(const T_vector &v, int add_val = 0) {
- for (int i = 0; i < int(v.size()); i++) cout << v[i] + add_val << (i != int(v.size()) - 1 ? ' ' : '\n');
- }
- // usage:
- // auto fun = [&](int i, int j) { return min(i, j); };
- // SparseTable<int, decltype(fun)> st(a, fun);
- // or:
- // SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
- template <typename T, class F = function<T(const T&, const T&)>>
- class SparseTable {
- public:
- int n;
- vector<vector<T>> mat;
- F func;
- SparseTable(const vector<T>& a, const F& f) : func(f) {
- n = static_cast<int>(a.size());
- int max_log = 32 - __builtin_clz(n);
- mat.resize(max_log);
- mat[0] = a;
- for (int j = 1; j < max_log; j++) {
- mat[j].resize(n - (1 << j) + 1);
- for (int i = 0; i <= n - (1 << j); i++) {
- mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
- }
- }
- }
- T get(int from, int to) const {
- assert(0 <= from && from <= to && to <= n - 1);
- int lg = 32 - __builtin_clz(to - from + 1) - 1;
- return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
- }
- };
- vector<vector<int>> adj;
- vector<bool> vis;
- vector<int> depth;
- vector<int> node_track;
- vector<int> last;
- vector<int> tree_depth;
- int tour_index;
- void visit(int node, int d) {
- node_track[tour_index] = node;
- depth[tour_index] = d;
- last[node] = tour_index;
- tour_index += 1;
- }
- void dfs(int cur, int par, int d) {
- tree_depth[cur] = d;
- visit(cur, d);
- for (int node : adj[cur]) {
- if (node == par) continue;
- dfs(node, cur, d + 1);
- visit(cur, d);
- }
- }
- void solve() {
- int n;
- cin >> n;
- adj = vector<vector<int>>(n);
- vis = vector<bool>(n);
- depth = vector<int>(2 * n - 1);
- node_track = vector<int>(2 * n - 1);
- last = vector<int>(n);
- tree_depth = vector<int>(n);
- vector<int> a(n);
- for (int i = 0; i < n - 1; i++) {
- int u, v;
- cin >> u >> v;
- --u, --v;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- tour_index = 0;
- dfs(0, -1, 0);
- SparseTable<int> sp(depth, [](int i, int j) {return min(i, j);});
- auto get_lca = [&](int a, int b) {
- int l = min(last[a], last[b]);
- int r = max(last[a], last[b]);
- return node_track[sp.get(l, r)];
- };
- int q;
- cin >> q;
- while (q--) {
- int k;
- cin >> k;
- vector<int> check(k);
- for (int &i : check) {
- cin >> i;
- --i;
- }
- if (k <= 2) {
- cout << "YES" << '\n';
- continue;
- }
- sort(check.rbegin(), check.rend(),
- [&](int a, int b) { return tree_depth[a] < tree_depth[b]; });
- int present = check[0];
- int idx = 0;
- for (int i = 1; i < k; i++) {
- present = get_lca(present, check[i]);
- if (present == check[i]) {
- continue;
- }
- idx = i + 1;
- break;
- }
- bool ans = true;
- int left = check[idx - 2], right = check[idx - 1];
- for (int i = idx; i < k; i++) {
- int with_present = get_lca(present, check[i]);
- int with_left = get_lca(check[i], left);
- int with_right = get_lca(check[i], right);
- ans &= with_present == present;
- ans &= with_left == present or with_left == check[i];
- ans &= with_right == present or with_right == check[i];
- }
- cout << (ans ? "YES" : "NO") << '\n';
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- #ifndef AQIB_DEBUG
- cin.tie(nullptr);
- #endif
- int t;
- cin >> t;
- while (t--) solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement