Dang_Quan_10_Tin

Untitled

Feb 23rd, 2020 (edited)
292
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. constexpr int N = 2e5 + 5;
  6. int n, q;
  7. int x[N], l, k, in[N];
  8. vector<int> adj[N];
  9.  
  10. int par[N][19], ranks[N];
  11.  
  12. void Read()
  13. {
  14.     cin >> n >> q;
  15.  
  16.     for (int i = 1; i < n; ++i)
  17.     {
  18.         int u, v;
  19.         cin >> u >> v;
  20.  
  21.         adj[u].emplace_back(v);
  22.         adj[v].emplace_back(u);
  23.     }
  24. }
  25.  
  26. void dfs(int v)
  27. {
  28.     in[v] = ++l;
  29.  
  30.     for (int i = 1; i < 19; ++i)
  31.         par[v][i] = par[par[v][i - 1]][i - 1];
  32.  
  33.     for (auto i : adj[v])
  34.         if (i != par[v][0])
  35.         {
  36.             ranks[i] = ranks[v] + 1;
  37.             par[i][0] = v;
  38.  
  39.             dfs(i);
  40.         }
  41. }
  42.  
  43. int LCA(int u, int v)
  44. {
  45.     if (ranks[u] < ranks[v])
  46.         swap(u, v);
  47.  
  48.     for (int i = 18; ~i; --i)
  49.         if (ranks[par[u][i]] >= ranks[v])
  50.             u = par[u][i];
  51.  
  52.     if (u == v)
  53.         return u;
  54.  
  55.     for (int i = 18; ~i; --i)
  56.         if (par[u][i] != par[v][i])
  57.         {
  58.             u = par[u][i];
  59.             v = par[v][i];
  60.         }
  61.  
  62.     return par[u][0];
  63. }
  64.  
  65. #define d(x, y) (ranks[x] + ranks[y] - 2 * ranks[LCA(x, y)])
  66.  
  67. void Solve()
  68. {
  69.     ranks[1] = 1;
  70.     dfs(1);
  71.  
  72.     while (q--)
  73.     {
  74.         cin >> k;
  75.  
  76.         for (int i = 1; i <= k; ++i)
  77.             cin >> x[i];
  78.  
  79.         sort(x + 1, x + k + 1, [&](const int &x, const int &y)
  80.              { return in[x] < in[y]; });
  81.  
  82.         int ans(0);
  83.  
  84.         for (int i = 1; i < k; ++i)
  85.             ans += d(x[i], x[i + 1]);
  86.         ans += d(x[1], x[k]);
  87.  
  88.         cout << ans / 2 << '\n';
  89.     }
  90. }
  91.  
  92. int32_t main()
  93. {
  94.     ios::sync_with_stdio(0);
  95.     cin.tie(0);
  96.     cout.tie(0);
  97.     Read();
  98.     Solve();
  99. }
  100.  
Add Comment
Please, Sign In to add comment