fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e5 + 5;
  4. const int inf = 1e9 + 7;
  5. int n, q, a[N];
  6. vector<int> adj[N];
  7. vector<int> V;
  8. int cnt[N];
  9. bool check[N];
  10. //
  11. int timer = 0, in[N], out[N], par[N][18], depth[N];
  12. void dfs(int u) {
  13.     in[u] = ++timer;
  14.     for(auto v : adj[u]) {
  15.         if(v == par[u][0]) continue;
  16.         par[v][0] = u;
  17.         depth[v] = depth[u] + 1;
  18.         for(int i = 1; i <= 17; i++) par[v][i] = par[par[v][i - 1]][i - 1];
  19.         dfs(v);
  20.     }
  21.     out[u] = timer;
  22. }
  23. int lca(int u, int v) {
  24.     if(depth[u] < depth[v]) swap(u, v);
  25.     for(int i = 17; i >= 0; i--) if(((depth[u] - depth[v]) >> i) & 1) u = par[u][i];
  26.     if(u == v) return u;
  27.     for(int i = 17; i >= 0; i--) {
  28.         if(par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
  29.     }
  30.     return par[u][0];
  31. }
  32. bool inside(int u, int v) {
  33.     return in[u] <= in[v] && out[u] >= out[v];
  34. }
  35. //
  36. long long dp[N];
  37. vector<int> g[N];
  38. void calc() {
  39.     vector<int> &node = V;
  40.     if(node.empty()) return;
  41.     sort(node.begin(), node.end(), [&] (int &a, int &b) {
  42.          return in[a] < in[b];
  43.     });
  44.     int k = node.size();
  45.     for(int i = 0; i < k - 1; i++) node.push_back(lca(node[i], node[i + 1]));
  46.     sort(node.begin(), node.end(), [&] (int &a, int &b) {
  47.          return in[a] < in[b];
  48.     });
  49.     node.erase(unique(node.begin(), node.end()), node.end());
  50.     k = node.size();
  51.     stack<int> st;
  52.     st.push(node[0]);
  53.     for(int i = 1; i < k; i++) {
  54.         while(!inside(st.top(), node[i])) st.pop();
  55.         g[st.top()].push_back(node[i]);
  56.         if(check[st.top()] && check[node[i]] && depth[st.top()] + 1 == depth[node[i]]) {
  57.             cout << -1 << '\n';
  58.             return;
  59.         }
  60.         st.push(node[i]);
  61.     }
  62.     int ans = 0;
  63.     for(auto x:node) 
  64.     {
  65.     	cout<<x<<endl;
  66.     	for(auto u:g[x]) cout<<u<<" ";
  67.     	cout<<endl;
  68.     }
  69.     cout<<endl;
  70.     reverse(node.begin(), node.end());
  71.     for(auto u : node) {
  72.         for(auto v : g[u]) cnt[u] += cnt[v];
  73.         if(check[u]) {
  74.             for(auto v : g[u]) if(cnt[v] > 0) ans++;
  75.             cnt[u] = 1;
  76.         }
  77.         else {
  78.             if(cnt[u] > 1) ans++, cnt[u] = 0;
  79.         }
  80.      }
  81.     cout << ans << '\n';
  82.     for(int i = 0; i < k; i++) g[node[i]].clear(), cnt[node[i]] = 0, check[node[i]] = 0;
  83. }
  84. void Solve() {
  85.     cin >> n;
  86.     for(int i = 1; i <= n - 1; i++) {
  87.         int u, v; cin >> u >> v;
  88.         adj[u].push_back(v);
  89.         adj[v].push_back(u);
  90.     }
  91.     dfs(1);
  92.     cin >> q;
  93.     while(q--) {
  94.         int k; cin >> k;
  95.         V.clear();
  96.         for(int i = 1; i <= k; i++) {
  97.             int x; cin >> x;
  98.             V.push_back(x);
  99.             cnt[x] = check[x] = 1;
  100.         }
  101.         calc();
  102.         for(auto u : V)  g[u].clear(), cnt[u] = check[u] = 0;
  103.     }
  104.  
  105. }
  106. int main() {
  107.     ios_base::sync_with_stdio(false);
  108.     cin.tie(NULL); cout.tie(NULL);
  109.     Solve();
  110. }
  111.  
Success #stdin #stdout 0.01s 11568KB
comments (?)
stdin
copy 
7
1 2
2 3
3 4
1 5
5 6
5 7
1
4 2 4 6 7
stdout
copy 
1
2 5 
2
4 
4

5
6 7 
6

7


2
https://ideone.com/nHCTC7
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!