Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #define debug(tl) cerr<<#tl<<' '<<tl<<'\n';
- #include "bits/stdc++.h"
- using namespace std;
- #define all(d) d.begin(), d.end()
- vector<vector<int>> gr;
- int t;
- vector<int> siz, tin, tout, head, p, h;
- void sizes(int v, int pr) {
- p[v] = pr, siz[v] = 1;
- if (pr != 0) h[v] = h[pr] + 1;
- gr[v].erase(find(all(gr[v]), pr));
- for (int& u : gr[v]) {
- sizes(u, v);
- siz[v] += siz[u];
- if (siz[u] > siz[gr[v][0]]) {
- swap(u, gr[v][0]);
- }
- }
- }
- void hld(int v) {
- tin[v] = t++;
- for (int& u : gr[v]) {
- if (u == gr[v][0]) head[u] = head[v];
- else head[u] = u;
- hld(u);
- }
- tout[v] = t;
- }
- bool ancestor(const int& u, const int& v) {
- return tin[u] <= tin[v] && tout[u] > tin[v];
- }
- void func(int u, int v, set<int> &k) {
- if (k.empty())return;
- int g = tin[u], ff = tin[v];
- auto l = k.lower_bound(tin[u]), r = k.upper_bound(tin[v]);
- vector<int> er;
- for (auto it = l; it != r; it++) {
- er.push_back(*it);
- }
- for (int& i : er) {
- k.erase(i);
- }
- }
- inline void up(int& u, int& v, set<int> &k) {
- while (!ancestor(head[u], v)) {
- func(head[u], u, k);
- u = p[head[u]];
- }
- }
- bool erase_try(int u, int v, set<int> &k) {
- up(u, v, k);
- up(v, u, k);
- if (!ancestor(u, v)) swap(u, v);
- func(u, v, k);
- return (int)k.size() == 0;
- }
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- t = 0;
- gr.clear(), siz.clear(), tin.clear(), tout.clear(), head.clear(), p.clear(), h.clear();
- int n; cin >> n;
- gr.resize(n), siz.resize(n), tin.resize(n), tout.resize(n), head.resize(n), p.resize(n), h.resize(n,0);
- gr[0].push_back(0);
- for (int i = 0; i < n - 1; i++) {
- int u, v; cin >> u >> v;
- u--, v--;
- gr[u].push_back(v);
- gr[v].push_back(u);
- }
- sizes(0, 0);
- hld(0);
- int q;
- cin >> q;
- for (int i = 0; i < q; i++) {
- int x; cin >> x;
- vector<int> p(x);
- for (int j = 0; j < x; j++) {
- cin >> p[j];
- p[j]--;
- }
- auto cmp = [&](const int& u, const int& v) {
- return h[u] < h[v];
- };
- sort(all(p), cmp);
- reverse(all(p));
- int u = p[0], v = p.back();
- for (int i = 1; i < (int)p.size(); i++) {
- if (!ancestor(p[i], u)) {
- v = p[i];
- break;
- }
- }
- set<int> k;
- for (int i = 0; i < (int)p.size(); i++) {
- if (p[i] != u && p[i] != v) {
- k.insert(tin[p[i]]);
- }
- }
- if (erase_try(u, v, k)) {
- cout << "YES\n";
- }
- else {
- cout << "NO\n";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement