fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1e5;
  9. const int max_log = 20;
  10. const int INF = 1e9;
  11.  
  12. int n, q, type[maxn + 10], tin[maxn + 10], tout[maxn + 10], h[maxn + 10], timer = 0;
  13. int par[maxn + 10][max_log + 5];
  14. ll dp[maxn + 10][2];
  15. vector<int> adj[maxn + 10], mini_adj[maxn + 10], stk, v_list;
  16. bool flag = 0;
  17.  
  18. void dfs(int top, int p = -1)
  19. {
  20.     tin[top] = ++timer;
  21.     for (int next_top : adj[top])
  22.     {
  23.         if (next_top == p)
  24.             continue;
  25.         par[next_top][0] = top;
  26.         h[next_top] = h[top] + 1;
  27.         dfs(next_top, top);
  28.     }
  29.     tout[top] = timer;
  30. }
  31. void build_lca()
  32. {
  33.     for (int j = 1; j <= max_log; j++)
  34.         for (int i = 1; i <= n; i++)
  35.             par[i][j] = par[par[i][j - 1]][j - 1];
  36. }
  37. bool is_par(int x, int y)
  38. {
  39.     if (!tin[x])
  40.         return 1;
  41.     return tin[x] <= tin[y] && tin[y] <= tout[x];
  42. }
  43. int get_lca(int x, int y)
  44. {
  45.     if (is_par(x, y))
  46.         return x;
  47.     if (is_par(y, x))
  48.         return y;
  49.     for (int j = max_log; j >= 0; j--)
  50.         if (!is_par(par[x][j], y))
  51.             x = par[x][j];
  52.     return par[x][0];
  53. }
  54. bool cmp(int a, int b)
  55. {
  56.     return tin[a] < tin[b];
  57. }
  58. void build_mini_graph()
  59. {
  60.     sort(v_list.begin(), v_list.end(), cmp);
  61.     int k = v_list.size();
  62.     for (int i = 1; i < k; i++)
  63.         v_list.push_back(get_lca(v_list[i - 1], v_list[i]));
  64.     sort(v_list.begin(), v_list.end(), cmp);
  65.     v_list.resize(unique(v_list.begin(), v_list.end()) - v_list.begin());
  66.     stk.clear();
  67.     for (int x : v_list)
  68.     {
  69.         while (stk.size() && !is_par(stk.back(), x))
  70.             stk.pop_back();
  71.         if (stk.size())
  72.             mini_adj[stk.back()].push_back(x);
  73.         stk.push_back(x);
  74.     }
  75. }
  76. void dp_on_tree(int top, int p = -1)
  77. {
  78.     int cnt_v = 0;
  79.     ll sum_0 = 0;
  80.     ll sum_1 = 0;
  81.     ll mn = 0;
  82.     for (int next_top : mini_adj[top])
  83.     {
  84.         if (next_top == p)
  85.             continue;
  86.         dp_on_tree(next_top, top);
  87.         cnt_v += type[next_top] && (h[next_top] - h[top] == 1);
  88.         sum_0 += dp[next_top][0];
  89.         mn += min(dp[next_top][1] + 1, dp[next_top][0]);
  90.         sum_1 += min(dp[next_top][0], dp[next_top][1]);
  91.     }
  92.     if (type[top] && cnt_v)
  93.         flag = 1;
  94.     if (!type[top])
  95.         dp[top][0] = min(sum_0, sum_1 + 1);
  96.     else
  97.         dp[top][1] = 0;
  98.     for (int next_top : mini_adj[top])
  99.     {
  100.         if (next_top == p)
  101.             continue;
  102.         if (type[top])
  103.             dp[top][1] += min(dp[next_top][0], dp[next_top][1] + 1);
  104.         else if (cnt_v <= 1)
  105.             dp[top][1] = min(dp[top][1], mn - min(dp[next_top][0], dp[next_top][1] + 1) + dp[next_top][1]);
  106.     }
  107.     if (mini_adj[top].size() == 0 && top != v_list[0])
  108.         if (type[top])
  109.             dp[top][1] = 0;
  110.         else
  111.             dp[top][0] = dp[top][1] = 0;
  112. //    cout << top << ' ' << dp[top][0] << ' ' << dp[top][1], el;
  113. }
  114.  
  115. int main()
  116. {
  117.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  118.     if (fopen("BODINH.INP", "r"))
  119.     {
  120.         freopen("BODINH.INP", "r", stdin);
  121.         freopen("BODINH.OUT", "w", stdout);
  122.     }
  123.  
  124.     cin >> n;
  125.     for (int i = 1; i < n; i++)
  126.     {
  127.         int x, y;
  128.         cin >> x >> y;
  129.         adj[x].push_back(y);
  130.         adj[y].push_back(x);
  131.     }
  132.     dfs(1);
  133.     build_lca();
  134.     for (int i = 1; i <= n; i++)
  135.         dp[i][0] = dp[i][1] = INF;
  136.     cin >> q;
  137.     while (q--)
  138.     {
  139.         flag = 0;
  140.         int k;
  141.         cin >> k;
  142.         for (int i = 1; i <= k; i++)
  143.         {
  144.             int x;
  145.             cin >> x;
  146.             v_list.push_back(x);
  147.             type[x] = 1;
  148.         }
  149.  
  150.         build_mini_graph();
  151.         dp_on_tree(v_list[0]);
  152.         if (flag)
  153.             cout << -1, el;
  154.         else
  155.             cout << min(dp[v_list[0]][0], dp[v_list[0]][1]), el;
  156.         for (int x : v_list)
  157.         {
  158. //            cout << x << ' ';
  159.             type[x] = 0;
  160.             dp[x][0] = dp[x][1] = INF;
  161.             mini_adj[x].clear();
  162.         }
  163.         v_list.clear();
  164.     }
  165. }
  166.  
Success #stdin #stdout 0.01s 8492KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/fiqof0
language:
C++14 (gcc 8.3)
created:
3 days 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!