Dang_Quan_10_Tin

D

Jul 22nd, 2020
246
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_map>
  4. #include <cstdio>
  5. #include <algorithm>
  6. using namespace std;
  7. using ll = long long;
  8. using ld = long double;
  9.  
  10. const int N = 2e5 + 2;
  11. vector<int> adj[N];
  12. int n, q, m, k, a[N * 3];
  13. int now[N], ranks[N], par[19][N];
  14. unordered_map<int, int> s[N];
  15.  
  16. void Read(){
  17.     cin >> n >> q;
  18.     for(int i = 1; i < n; ++i){
  19.         int u, v;
  20.         cin >> u >> v;
  21.         adj[u].push_back(v);
  22.         adj[v].push_back(u);
  23.     }
  24. }
  25.  
  26. void dfs(int v){
  27.     now[v] = ++m;
  28.     for(int i = 1; i <= 18; ++i)
  29.         par[i][v] = par[i - 1][par[i - 1][v]];
  30.     for(int i : adj[v])
  31.         if(ranks[i] == 0){
  32.             ranks[i] = ranks[v] + 1;
  33.             par[0][i] = v;
  34.             dfs(i);
  35.         }
  36. }
  37.  
  38. int find_lca(int u, int v){
  39.     if(ranks[u] < ranks[v])
  40.         swap(u, v);
  41.     for(int i = 18; ~i; --i)
  42.         if(ranks[par[i][u]] >= ranks[v])
  43.             u = par[i][u];
  44.     if(u == v)
  45.         return u;
  46.     for(int i = 18; ~i; --i)
  47.         if(par[i][u] != par[i][v])
  48.             u = par[i][u],
  49.             v = par[i][v];
  50.     return par[0][u];
  51. }
  52.  
  53. int LCA(int u, int v){
  54.     int &x = s[u][v];
  55.     if(x != 0)
  56.         return x;
  57.     return x = find_lca(u, v);
  58. }
  59.  
  60. void Solve(){
  61.     cin >> k;
  62.     for(int i = 1; i <= k; ++i)
  63.         cin >> a[i];
  64.     sort(a + 1, a + k + 1, [] (const int &x, const int &y){return now[x] < now[y];});
  65.     a[k + 1] = a[1];
  66.     int ans = 0;
  67.     for(int i = 1; i <= k; ++i){
  68.         int t = LCA(a[i], a[i + 1]);
  69.         ans += ranks[a[i]] + ranks[a[i + 1]] - 2 * ranks[t];
  70.     }
  71.     cout << ans / 2 << "\n";
  72. }
  73.  
  74. main(){
  75.     ios::sync_with_stdio(0);
  76.     cin.tie(0);
  77.     cout.tie(0);
  78.     Read();
  79.     ranks[1] = 1; dfs(1);
  80.     while(q--)
  81.         Solve();
  82. }
Advertisement
Add Comment
Please, Sign In to add comment