?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
169330410 |
Дорешивание: chengchunhao |
1328E - 12 | C++17 (GCC 7-32) | Полное решение | 374 мс | 31984 КБ | 2022-08-22 15:08:23 | 2022-08-22 15:08:23 |
#include <bits/stdc++.h> #define EB emplace_back using std::cin; using std::cout; using std::vector; const int N = 200005; int n, q; int dep[N], p[20][N]; vector <int> G[N]; void dfs(int u, int fa) { dep[u] = dep[fa] + 1; p[0][u] = fa; for (int i = 1; i <= 19; ++i) p[i][u] = p[i - 1][p[i - 1][u]]; for (auto v : G[u]) if (v != fa) { dfs(v, u); } } bool is_ancestor(int u, int v) { for (int i = 19; i >= 0; --i) if ((dep[v] - dep[u]) & (1 << i)) v = p[i][v]; return u == v; } int main() { std::ios::sync_with_stdio(false), cin.tie(nullptr); int u, v, m; cin >> n >> q; for (int i = 1; i < n; ++i) { cin >> u >> v; G[u].EB(v); G[v].EB(u); } dfs(1, 0); while (q--) { cin >> m; vector <int> v(m); int end = 0; for (int i = 0; i < m; ++i) { cin >> v[i], v[i] = p[0][v[i]]; if (dep[v[i]] > dep[end]) end = v[i]; } bool ok = true; for (int i = 0; i < m; ++i) ok &= is_ancestor(v[i], end); cout << (ok ? "YES" : "NO") << '\n'; } return 0; }
?
?
?
?