Advertisement
he_obviously

Untitled

Jan 11th, 2021
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.60 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <iostream>
  4. #include <vector>
  5. #include <set>
  6. #include <map>
  7. #include <unordered_set>
  8. #include <unordered_map>
  9. #include <string>
  10. #include <cmath>
  11. #include <climits>
  12. #include <algorithm>
  13. #include <random>
  14. #include <iomanip>
  15. #include <ctime>
  16. #include <queue>
  17. #include <utility>
  18. #include <fstream>
  19. #include <bitset>
  20.  
  21. typedef long long ll;
  22. typedef long double ld;
  23.  
  24. using namespace std;
  25.  
  26. #define all(x) (x).begin(),(x).end()
  27. #define sz(x) (int)x.size()
  28.  
  29. int n, q, logn = 0, timer = 0, ki;
  30. vector<vector<int>> g, p, sparse;
  31. vector<int> tin, tout, sz_subtree, d, k, first, logs, order;
  32. vector<vector<pair<int, int>>> sz;
  33.  
  34. void dfs(int v, int par) {
  35.     tin[v] = timer;
  36.     ++timer;
  37.     p[v][0] = par;
  38.     for (int i = 1; i < logn; ++i) {
  39.         p[v][i] = p[p[v][i - 1]][i - 1];
  40.     }
  41.     for (int x : g[v]) {
  42.         if (x != par) {
  43.             dfs(x, v);
  44.         }
  45.     }
  46.     tout[v] = timer;
  47.     ++timer;
  48. }
  49.  
  50. void size_dfs(int v, int par) {
  51.     sz_subtree[v] = 1;
  52.     for (int x : g[v]) {
  53.         if (x != par) {
  54.             size_dfs(x, v);
  55.             sz_subtree[v] += sz_subtree[x];
  56.             sz[x].push_back({ v, n - sz_subtree[x] });
  57.         }
  58.     }
  59.     if (par != -1)
  60.         sz[par].push_back({ v, sz_subtree[v] });
  61. }
  62.  
  63. void depth_dfs(int v, int par, int _h) {
  64.     d[v] = _h;
  65.     order.push_back(v);
  66.     for (int x : g[v]) {
  67.         if (x != par) {
  68.             depth_dfs(x, v, _h + 1);
  69.             order.push_back(v);
  70.         }
  71.     }
  72. }
  73.  
  74. int lca(int a, int b) {
  75.     int left = first[a], right = first[b];
  76.     if (left > right) swap(left, right);
  77.     right += 1;
  78.     int log = logs[right - left];
  79.     int ans1 = sparse[log][left], ans2 = sparse[log][right - (1 << log)];
  80.     return (d[ans1] < d[ans2] ? ans1 : ans2);
  81. }
  82.  
  83. int dist(int v, int u) {
  84.     return d[v] + d[u] - 2 * d[lca(u, v)];
  85. }
  86.  
  87. void solve() {
  88.     int ans = 0;
  89.     int s = k[0];
  90.     vector<int> x;
  91.     for (int i = 1; i < ki; ++i) {
  92.         int v = lca(s, k[i]), len = dist(s, k[i]);
  93.         int need_len = len / 2 + 1;
  94.         int xx;
  95.         if (d[s] - d[v] >= need_len) {
  96.             int ss = s;
  97.             for (int l = logn - 1; l >= 0; --l) {
  98.                 int u = p[ss][l];
  99.                 if (d[s] - d[u] <= need_len)
  100.                     ss = u;
  101.             }
  102.             xx = ss;
  103.         }
  104.         else {
  105.             need_len = (len - 1) / 2;
  106.             int ss = k[i];
  107.             for (int l = logn - 1; l >= 0; --l) {
  108.                 int u = p[ss][l];
  109.                 if (d[k[i]] - d[u] <= need_len)
  110.                     ss = u;
  111.             }
  112.             xx = ss;
  113.         }
  114.         x.push_back(xx);
  115.     }
  116.     for (int i = 0; i < sz(x); ++i) {
  117.         for (int j = 0; j < sz(x); ++j) {
  118.             if (x[i] == -1 || x[j] == -1 || i == j)
  119.                 continue;
  120.             if (dist(s, x[i]) == dist(s, x[j]) + dist(x[j], x[i]))
  121.                 x[i] = -1;
  122.         }
  123.     }
  124.     for (int i = 0; i < sz(x); ++i) {
  125.         if (x[i] == -1)
  126.             continue;
  127.         int pr = -1;
  128.         for (int pp = 0; pp < sz(sz[x[i]]); ++pp) {
  129.             if (pr == -1 || dist(s, sz[x[i]][pp].first) < dist(s, sz[x[i]][pr].first))
  130.                 pr = pp;
  131.         }
  132.         ans += n - sz[x[i]][pr].second;
  133.     }
  134.     cout << n - ans << "\n";
  135. }
  136.  
  137. void stupid() {
  138.     vector<int> _used(n, 0);
  139.     queue<int> qq;
  140.     for (int i = 0; i < ki; ++i) {
  141.         _used[k[i]] = (i ? -1 : 1);
  142.         qq.push(k[i]);
  143.     }
  144.     while (!qq.empty()) {
  145.         int s = qq.front();
  146.         qq.pop();
  147.         for (int x : g[s]) {
  148.             if (!_used[x]) {
  149.                 _used[x] = _used[s];
  150.                 qq.push(x);
  151.             }
  152.         }
  153.     }
  154.     int ans = 0;
  155.     for (int i = 0; i < n; ++i) {
  156.         ans += (int)(_used[i] == 1);
  157.     }
  158.     cout << ans << "\n";
  159. }
  160.  
  161. int main() {
  162.  
  163.     ios_base::sync_with_stdio(0);
  164.     cin.tie(0); cout.tie(0);
  165.  
  166.     //reading
  167.     {
  168.         cin >> n >> q;
  169.  
  170.         while ((1 << logn) <= n)
  171.             ++logn;
  172.  
  173.         logs.resize(n + 1);
  174.         g.resize(n);
  175.         tin.resize(n);
  176.         tout.resize(n);
  177.         sz_subtree.resize(n);
  178.         d.resize(n);
  179.         k.resize(n);
  180.         p.resize(n, vector<int>(logn));
  181.         sz.resize(n);
  182.         first.resize(n, -1);
  183.  
  184.         for (int i = 0; i < n - 1; ++i) {
  185.             int a, b;
  186.             cin >> a >> b;
  187.             --a; --b;
  188.             g[a].push_back(b);
  189.             g[b].push_back(a);
  190.         }
  191.     }
  192.  
  193.     dfs(0, 0);
  194.     size_dfs(0, -1);
  195.     depth_dfs(0, -1, 0);
  196.  
  197.     logs.resize(sz(order) + 1);
  198.  
  199.     logs[1] = 0;
  200.     for (int i = 2; i < sz(order) + 1; ++i) {
  201.         if ((1 << (logs[i - 1] + 1)) <= i) {
  202.             logs[i] = logs[i - 1] + 1;
  203.         }
  204.         else {
  205.             logs[i] = logs[i - 1];
  206.         }
  207.     }
  208.  
  209.     for (int i = 0; i < sz(order); ++i) {
  210.         if (first[order[i]] == -1) {
  211.             first[order[i]] = i;
  212.         }
  213.     }
  214.  
  215.     sparse.resize(logs[sz(order)] + 1, vector<int>(sz(order)));
  216.  
  217.     for (int i = 0; i < sz(order); ++i) {
  218.         sparse[0][i] = order[i];
  219.     }
  220.  
  221.     for (int i = 1; i <= logs[sz(order)]; ++i) {
  222.         for (int j = 0; j + (1 << i) <= sz(order); ++j) {
  223.             int ans1 = sparse[i - 1][j], ans2 = sparse[i - 1][j + (1 << (i - 1))];
  224.             sparse[i][j] = (d[ans1] < d[ans2] ? ans1 : ans2);
  225.         }
  226.     }
  227.  
  228.     for (int _ = 0; _ < q; ++_) {
  229.         cin >> ki;
  230.         for (int i = 0; i < ki; ++i) {
  231.             cin >> k[i];
  232.             --k[i];
  233.         }
  234.         if (ki <= 20)
  235.             solve();
  236.         else
  237.             stupid();
  238.     }
  239.  
  240.     return 0;
  241.  
  242. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement