fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 200005;
  8. vector<int> adj[MAXN];
  9. int tin[MAXN], tout[MAXN], parent[MAXN], depth[MAXN];
  10. int timer;
  11.  
  12. void dfs(int v, int p, int d) {
  13.     tin[v] = ++timer;
  14.     parent[v] = p;
  15.     depth[v] = d;
  16.     for (int u : adj[v]) {
  17.         if (u != p) {
  18.             dfs(u, v, d + 1);
  19.         }
  20.     }
  21.     tout[v] = ++timer;
  22. }
  23.  
  24. bool is_ancestor(int u, int v) {
  25.     return tin[u] <= tin[v] && tout[u] >= tout[v];
  26. }
  27.  
  28. int main() {
  29.     ios_base::sync_with_stdio(false);
  30.     cin.tie(NULL);
  31.  
  32.     int n, m;
  33.     cin >> n >> m;
  34.  
  35.     for (int i = 0; i < n - 1; ++i) {
  36.         int u, v;
  37.         cin >> u >> v;
  38.         adj[u].push_back(v);
  39.         adj[v].push_back(u);
  40.     }
  41.  
  42.     dfs(1, 1, 0);
  43.  
  44.     while (m--) {
  45.         int k;
  46.         cin >> k;
  47.         vector<int> v(k);
  48.         int deepest_node = -1;
  49.         int max_depth = -1;
  50.  
  51.         for (int i = 0; i < k; ++i) {
  52.             cin >> v[i];
  53.             // Zamieniamy wierzchołek na jego ojca
  54.             v[i] = parent[v[i]];
  55.             // Szukamy najgłębszego wierzchołka w zbiorze ojców
  56.             if (depth[v[i]] > max_depth) {
  57.                 max_depth = depth[v[i]];
  58.                 deepest_node = v[i];
  59.             }
  60.         }
  61.  
  62.         bool possible = true;
  63.         for (int node : v) {
  64.             // Sprawdzamy, czy każdy "ojciec" jest przodkiem najgłębszego "ojca"
  65.             if (!is_ancestor(node, deepest_node)) {
  66.                 possible = false;
  67.                 break;
  68.             }
  69.         }
  70.  
  71.         if (possible) cout << "TAK\n";
  72.         else cout << "NIE\n";
  73.     }
  74.  
  75.     return 0;
  76. }
Success #stdin #stdout 0.01s 10132KB
comments (?)
stdin
copy 
10 6
1 2
1 3
1 4
2 5
2 6
3 7
7 8
7 9
9 10
4 3 8 9 10
3 2 4 6
3 2 1 5
3 4 8 2
2 6 10
3 5 4 7
stdout
copy 
TAK
TAK
TAK
TAK
NIE
NIE
https://ideone.com/tASrQ1
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!